Real-time scheduling of ensemble systems with limited resources
J.A.B. Fortes, Prapaporn Rattanatamrong · 2011
Inspired by the strategy of divide and conquer, ensemble systems utilize multiple simple computational models (called ‘experts’) that can, individually or in some combination, generate solutions for a larger range of input cases than their single original model. Real system requirements of ensemble systems (e.g., size, weight, power and cost constraints) often lead to limited availability of computational resources required to support concurrent execution of all experts. This dissertation proposes a generalized architecture, called Elastic Ensemble Scheduling (EES) manager, to address the problem of scheduling experts in ensemble systems in the way that the overall system performance is minimally affected by limited resources. The EES manager consists of a Task Utilization Adaptor (TUA), an adaptive Real-Time Scheduler (RTS) and a Fuzzy feedback controller (FZ). The TUA uses optimization techniques to determine the time-varying resource utilization required by each expert to ensure that critical experts achieve their best performance while guaranteeing minimum execution time needed by other experts. The RTS creates a schedule of expert execution that allows each task to achieve resource utilization as close as possible to its demand without any violation of time constraint or ensemble system's policies. In order to cope with uncertainty in the system and deployment environment, the FZ determines the total utilization allocation for the TUA so that the system fully utilizes the available resource capacity. The dissertation first considers when resources are dedicated and each expert has an accurate worst-case execution time (WCET) and presents the implementations of the EES manager for systems with uniform and non-uniform WCETs. Then, the EES manager is extended to support scheduling under uncertain resource availability and imprecise WCETs. From performance evaluation, experts in a resource-constrained case-study ensemble system scheduled with the EES manager are shown to produce system outputs closely similar (≤ 8% error) to those of the system with sufficient resources, although the limited-resource system has up to 40% less resources. The simulation results also show that execution-time imprecision and occasional fluctuation of resource capacity can be tolerated and demonstrate the EES manager's efficiency with reasonably small overheads in optimization, preemption and migration. (Full text of this dissertation may be available via the University of Florida Libraries web site. Please check http://www.uflib.ufl.edu/etd.html )