Scholarlink

<p>We study the problem of energy-efficient online execution of a complex task on a server with variable processing speed. The task consists of a set of stochastic elementary jobs structured as a Directed Acyclic Graph (DAG), where each job’s execution may reveal new information that influences future scheduling decisions. Our objective is to determine an online speed control policy that minimizes the expected energy consumption while ensuring that the task completes before a strict deadline. Leveraging tools from convex optimization, the optimality principle, and backward induction, we derive a structural characterization of the optimal policy. We find that this is linked to a set of second-order differential equations and exhibits a non-trivial form. Building on this result, we develop a discretization-based algorithm that efficiently approximates the optimal policy. The proposed algorithm is provably asymptotically exact in the discretization step and has computational complexity <i>O</i>(<i>AN</i>), where&#xa0;<i>A</i> denotes the number of edges in the underlying DAG and&#xa0;<i>N</i> is the size of the discretization. Our results offer a principled and computationally efficient solution framework for online execution of structured stochastic workloads under strict energy and timing constraints.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Time-constrained energy minimization for online execution of a stochastic DAG task

  • 期刊论文

  • 发表日期：

    2026年3月14日

查看全文
  • Jonatha Anselmi,
  • Bruno Gaujal,
  • Karl Gottlieb

摘要

We study the problem of energy-efficient online execution of a complex task on a server with variable processing speed. The task consists of a set of stochastic elementary jobs structured as a Directed Acyclic Graph (DAG), where each job’s execution may reveal new information that influences future scheduling decisions. Our objective is to determine an online speed control policy that minimizes the expected energy consumption while ensuring that the task completes before a strict deadline. Leveraging tools from convex optimization, the optimality principle, and backward induction, we derive a structural characterization of the optimal policy. We find that this is linked to a set of second-order differential equations and exhibits a non-trivial form. Building on this result, we develop a discretization-based algorithm that efficiently approximates the optimal policy. The proposed algorithm is provably asymptotically exact in the discretization step and has computational complexity O(AN), where A denotes the number of edges in the underlying DAG and N is the size of the discretization. Our results offer a principled and computationally efficient solution framework for online execution of structured stochastic workloads under strict energy and timing constraints.