Data-Intensive Distributed Systems LaboratoryProject -- Theory of Priority Scheduling Systems (Stefan Muller)
Many high-performance computing systems contain tasks of varying priority. Consider a file storage system that is constantly indexing and analyzing metadata in order to optimize search time as well as storage usage, but must also handle store and load requests: the analytics and optimization processes are low-priority background tasks but the requests must be handled quickly to keep the system responsive. In prior work, we have developed priority scheduling algorithms for such systems that provably respect bounds on how much a high-priority computation can be delayed by a lower-priority computation. The proof models a parallel computation as a dependency graph in which each graph node is assigned a priority, and a scheduler as a scheme for assigning graph nodes to processors respecting the dependencies. The result holds as long as the program is free of priority inversions, that is, no high-priority graph node can be caused to be unavailable by a low-priority node. We also developed a type system for a parallel language model that ensures that programs are free of this type of priority inversion.
While the language is usable for simple programs, it is not yet a fully-functional programming language. There are many challenges, both in implementation and in theory, in turning it into a more usable language, and thus many opportunities for student projects. One example is designing a module system that allows different libraries and modules to declare priorities and the ordering between them. Past undergraduate students on this project have extended the language to allow priorities of threads to be computed based on run-time conditions (rather than hard-coded), and to allow threads to change priorities while running.
Students with many levels of experience and courses taken can participate in the project. For example, the language and type systems extensions are suitable for students who have taken an upper-level programming languages course, while students who have had introductory algorithms and data structures coursework will likely be able to work on the time bound models and corresponding proofs. Students familiar with, or willing to learn, functional programming languages can work on implementing these features in the compiler for the language.