An Optimal Semi-partitioned Scheduler for Uniform Heterogeneous Multiprocessors

A semi-partitioned scheduler called EDF-tu is presented that is the first such scheduler to be optimal on uniform heterogeneous multiprocessors. EDF-tu utilizes an adjustable allocation parameter called a frame to schedule tasks that migrate. The frame size F must divide all task periods to ensure hard real-time optimality, but for any choice of F, maximum deadline tardiness is at most F. Thus, the proper selection of F hinges on runtime overheads (which are higher when F is smaller) and the strength of the real-time guarantee desired. When determining which tasks must migrate, new issues specific to heterogeneous platforms arise that have not been explored before. It is shown via counterexamples that resolving such issues differently from EDF-tu can render feasible task systems unschedulable.