Automatically Optimizing Caiman Schedules

[Checkmate50]

Caiman divides programs into a value language and a schedule language. Given a fixed program in the value language, you can write many different schedule programs, and the semantics are the same: i.e., the program produces the same output regardless of the schedule program. But the schedule determines performance: it gives the programmer control over the execution details that dictate whether the "same" computation goes fast or slow. This is where @mjguynn comes in!

The goal in this project is to automatically transform schedules that are already written in order to improve their performance. That is, we will start with a complete (valid) program in both the value language and the schedule language. Then, our proposed tool will try to transform that valid schedule into a new schedule that performs better. (It will not touch the value program.) This will require inventing some patterns for performance-improving transformations and implementing them in transformations on the Caiman RON-based IR.

1. Bikeshed scheduling optimizations and finish up work on experimentation [1-2 weeks]
2. Implement dumbest possible scheduling optimization on what exists from the frontend (may be written in hacky unfinished frontend AST depending on LIam's progress) [1-2 weeks]
3. Test optimization and/or develop timing script [1-2 weeks]
4. Writeup overview of scheduling constraints and possible optimizations [2 weeks]
5. Implement scheduling code on resulting frontend (which should be more complete at this point) [2-4 weeks]
6. Experiment with scheduling optimizations and identify strengths/weaknesses [2 weeks]
7. Writeup results [1 week]

As with #9, however, this is just a sketch of the plan! We need feedback and ideas about tweaks to both the high-level direction and the week-by-week execution plan. Please weigh in below!

[mjguynn]

The week-by-week schedule sounds good to me!

Is the goal limited to re-scheduling "explicit" data transfers, or does it also involve things like: x lives on the CPU, y lives on the CPU, you have y = x+ 5, choose where to schedule the addition? (Or is that an incorrect model of Caiman's current semantics?)