The Euromicro Conference on Real-Time Systems (ECRTS) presented its 2010 Best Paper award to Computer Science Ph.D. Students Greg Levin, Caitlin Sadowski and Ian Pye, CS Professor Scott Brandt, and their collaborator Shelby Funk (University of Georgia) for their work “DP-FAIR: A Simple Model for Understanding Optimal Multiprocessor Scheduilng.”

Multiprocessor systems are becoming commonplace as more computers have multiple cores. Many implications of using a multiprocessor system, including scheduling issues, are still not well understood. Multiprocessor scheduling is particularly difficult in the presence of real-time constraints. New research in the UCSC Systems Research Laboratory (SRL) addresses this challenging problem.

A number of recent papers have used the notions of fluid scheduling and deadline partitioning to guarantee optimality and improve performance. Levin et al. provide a unifying theory and examine how it overcomes problems faced by greedy scheduling algorithms. They discuss a simple DP-FAIR scheduling algorithm, DP-WRAP, which serves as a least common ancestor to many recent algorithms. They also show how to extend DP-FAIR to the scheduling sporadic task sets with arbitrary deadlines.

For more information about this research or the SRL, please contact Prof. Scott Brandt (scott@cs.ucsc.edu). More information about ECRTS 2010 can be found here: http://ecrts.eit.uni-kl.de/ecrts10