Metascheduling algorithm that implements a reconvergence of paths to manage the multi-schedule state-space problem of metascheduling.
Abstract
“Adaptation in time-triggered systems can be motivated by energy efficiency, fault recovery, and changing environmental conditions. Adaptation in time-triggered systems is achieved by preserving temporal predictability through metascheduling techniques. Nevertheless, utilising existing metascheduling schemes for time-triggered network-on-chip architectures poses design time computation and run-time storage challenges for adaptation using the resulting schedules. In this work, an algorithm for path reconvergence in a multi-schedule graph, enabled by a reconvergence horizon, is presented to manage the state-space explosion problem resulting from an increase in the number of scenarios required for adaptation. A meta-scheduler invokes a genetic algorithm to solve a new scheduling problem for each adaptation scenario, resulting in a multi-schedule graph. Finally, repeated nodes of the multi-schedule graph are merged, and further exploration of paths is terminated. The proposed algorithm is evaluated using various application model sizes and different horizon configurations. Results show up to 56% reduction of schedules necessary for adaptation to 10 context events, with the reconvergence horizon set to 50 time units. Furthermore, 10 jobs with 10 slack events and a horizon of 40 ticks result in a 23% average sleep time for energy savings. Furthermore, the results demonstrate the reduction in the state-space size while showing the trade-off between the size of the reconvergence horizon and the number of nodes of the multi-schedule graph.”
Find the open access technical paper here. Published 2022.
Muoka, P.; Onwuchekwa, D.; Obermaisser, R. Adaptive Scheduling for Time-Triggered Network-on-Chip-Based Multi-Core Architecture Using Genetic Algorithm. Electronics 2022, 11, 49. https://doi.org/10.3390/electronics11010049
Leave a Reply