Resource Management for Stochastic Parallel Synchronous Tasks: Bandits to the Rescue

Abstract In scheduling real-time tasks, we face the challenge of meeting hard deadlines while optimizing for some other objective, such as minimizing energy consumption. Formulating the optimization as a Multi-Armed Bandit (MAB) problem allows us to use MAB strategies to balance the exploitation of good choices based on observed data with the exploration of potentially better options. In this paper, we integrate hard real-time constraints with MAB strategies for resource management of a Stochastic Parallel Synchronous Task. On a platform with $$M$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>M</mml:mi> </mml:math> cores available for the task, $$m\le M$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>m</mml:mi> <mml:mo>≤</mml:mo> <mml:mi>M</mml:mi> </mml:mrow> </mml:math> cores are initially assigned. Prior work has shown how to compute a virtual deadline such that assigning all $$M$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>M</mml:mi> </mml:math> cores to the task if it has not completed by this virtual deadline guarantees that the deadline will be met. An MAB strategy is used to select the value of $$m$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>m</mml:mi> </mml:math> . A Dynamic Power Management (DPM) energy model considering CPU sockets and sleep states is described. Experimental evaluation shows that MAB strategies learn consistently suitable $$m$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>m</mml:mi> </mml:math> , and perform well compared to binary exponential search and greedy methods.