Dynamic scheduling of imprecise-computation tasks in maximizing QoS under energy constraints for embedded systems

In designing energy-aware CPU scheduling algorithms for real-time embedded systems, dynamic slack reclamation techniques significantly improve system quality-of-service (QoS) and energy efficiency. However, the limited schemes in this domain either demand high complexity or can only achieve limited QoS. In this paper, we present a novel low complexity runtime scheduling algorithm for the imprecise computation (IC) modeled tasks. The target is to maximize system QoS under energy constraints. Our proposed algorithm, named gradient curve shifting (GCS), is able to decide the best allocation of slack cycles arising at runtime, with very low complexity. We study both linear and concave QoS functions associated with IC modelde tasks, on non-DVS and DVS processors. Furthermore, we apply the intra-task DVS technique to tasks and achieve as large as 18% more of the system QoS compared to the conventional "optimal" solution which is inter-task DVS based.