Development of Markov-Chain Prediction Model for Work-Stealing Scheduler in Dynamic Scheduling for Multicore Embedded Software Systems

Designing embedded software that achieves effective utilization of the fast-growing multicore embedded hardware should help to reduce their execution time and power consumption and improve their reliability. AI and machine learning algorithms are making their way into such rapidly enhanced multicore embedded hardware. We have developed a Markov-chain prediction model and integrated it into a work-stealing scheduler within a dynamic scheduling runtime layer (DSRL). Dynamic scheduling with a work-stealing scheduler was adapted from MIT’s Cilk framework. Dynamic scheduling allows independent computations to be spawned so they can be scheduled dynamically and executed in parallel on available cores. Cilk used a random model in its work-stealing scheduler where an idle core randomly selects other cores to steal computations from them. However, our Markov-chain-based scheduler allows idle cores to make informed decisions about which cores are better to steal their computation to increase parallel executions and improve load balancing and resource utilization. We have implemented the DSRL with our proposed Markov-chain-based predictive work-stealing scheduler on QNX multicore RTOS and tested it using a 4-core NXP SBC-S32V234 development board. For performance evaluation, we have implemented a Mandelbrot sample application. We forked parallelizable functions inside two tasks running on 2 cores to be dynamically scheduled and executed in parallel on the third core, while the fourth core drives the application. Preliminary results showed that our Markov chain prediction model outperformed the traditional random model with a 1.6x speedup compared to 1.2x in the application’s execution time. This paper provides a detailed description of the Markov chain mathematical prediction model, its integration in the work-stealing scheduler of the DSRL layer, and its application to embedded systems. This work is a part of ongoing research, and this paper discusses current challenges and future work for enhancing the scalability and performance of embedded software using this prediction model.