arXiv:2605.27652v1 [cs.DC] 26 May 2026
Carbon-Aware Mapping and Scheduling for Deadline-Constrained Workflows Dominik Schweisgut∗
Anne Benoit†
Yves Robert‡
Henning Meyerhenke§
Abstract As datacenters continue to grow in scale, their energy consumption and resulting carbon footprint have become pressing concerns. With the increasing share of renewable energy in a datacenter’s mixed energy supply, shifting task execution to periods of high green-power availability is a promising strategy to reduce carbon emissions. However, in heterogeneous computing environments, the power consumption of compute nodes in a datacenter can also vary. In practice, workloads submitted to datacenters are often not isolated tasks, but entire workflows consisting of interdependent tasks with precedence constraints. A further challenge arises from the fact that carbon emission reductions must typically be achieved under strict workflow deadlines. In this work, we show that the problem posed by these challenges for the scheduler is NP-hard and admits no constant-factor approximation even for the uni-processor case. Motivated by this hardness, we present a novel algorithm CWM that combines carbon-aware mapping and scheduling to construct feasible solutions. Our approach integrates dynamic programming with efficient heuristics to exploit renewable energy availability and infrastructure heterogeneity. To assess the quality of the new algorithm, we evaluate it against the stateof-the-art approach CaWoSched and show that CWM achieves significant reductions in terms of carbon emissions in experiments. In particular, we are able to achieve a median carbon cost reduction of 42% over the best version of CaWoSched when the deadline is two times the makespan of a carbon-agnostic baseline. Note that CaWoSched itself already reduces the carbon-agnostic baseline by 36%.
Keywords: Workflow scheduling algorithms Carbon-aware computing DAG scheduling Heterogeneous platforms Mapping ∗ Karlsruhe Institute of Technology (KIT), Germany, [email protected] † ENS Lyon, France, [email protected] ‡ ENS Lyon, France, [email protected] § Karlsruhe Institute of Technology (KIT), Germany, [email protected]
1
1
Introduction
The growing awareness of environmental concerns and increasingly stringent regulations are pushing all manufacturing entities towards reducing the carbon footprint of their operations [20]. Data/computing centers are also particularly affected as they represent a steadily increasing fraction of carbon emissions [2]. In this context, data/computing centers have started to use a mix of different power sources, giving priority to lower carbon-emitting technologies (solar, wind, nuclear) over higher ones (coal, natural gas). This has motivated growing interest in carbon-aware scheduling as a promising technique for lowering the carbon footprint of computations and data accesses, by accounting for the time-dependent carbon intensity of the power grid and the varying availability of renewable electricity sources. While carbon-aware scheduling introduces new challenges, it also brings new opportunities for HPC scientists. This is exemplified by this work focusing on scheduling application workflows on platforms whose power mix differs over time. On the one hand, this is a challenging endeavor because designing efficient scheduling algorithms was already difficult (NP-complete in most scenarios) when computers were powered by a single energy source with a constant level of carbon emissions. On the other hand, the availability of greener time intervals is a great opportunity to revisit well-known algorithms: intuitively, one would aim at shifting tasks away from high-carbon emitting intervals, while maintaining good overall performance. More specifically, this work deals with scientific applications that consist of workflow graphs, where nodes represent tasks and edges represent inter-task dependencies. Many workloads in data/computing centers can be expressed as such workflows, and the scheduling literature is rich of algorithms and complexity results. The typical objective used to be the minimization of the total execution time (also called makespan). In recent years, objectives beyond makespan (total energy consumption [23], reliability [15]) have also been studied in multi-objective trade-offs, aiming at minimizing one metric while guaranteeing some threshold on other metrics, e.g., minimizing energy consumption while enforcing a makespan threshold. But all these approaches rely on a stable platform whose characteristics do not vary over time. A major novelty with regards to carbon emissions is that the platform is changing over time, alternating greener and browner intervals for carbon emissions, and thereby calling for new algorithms. A partial solution to the problem appeared in our previous work [25], where we focus on carbon minimization at the price of a restrictive assumption: that the mapping and ordering of the workflow tasks are given (say using the wellknown HEFT algorithm [27]), together with a time deadline to complete the execution. The rule of the game is then to shift tasks across carbon intervals on each processor so as to minimize carbon emissions while maintaining the deadline. This restricted focus turns out to be sufficient to gain significant reduction of carbon emissions for a comprehensive set of experiments [25]. This work builds on the results of [25], but addresses a combinatorially much more difficult problem: rather than fixing the mapping and ordering upfront (e.g., via HEFT), we jointly optimize mapping and scheduling, facing a much larger 2
search space, and assess the gains that can be expected from this holistic approach. We stress that we target heterogeneous clusters whose processors have different speeds and different energy profiles. Contributions. The main contributions of this paper are threefold: (i) on the theory side, the proof that no approximation up to a constant factor exists for the simple problem instance with a unique processor (unless P=NP); (ii) the design of sophisticated carbon-aware mapping and scheduling algorithms with more flexibility and higher quality than state-of-the-art solutions such as [25]; and (iii) their empirical assessment through a comprehensive campaign of simulations. Not surprisingly, the experiments demonstrate a major gain over a carbon-unaware approach. More importantly, they further improve significantly two state-of-the-art algorithms from [25] that carbon-optimize a mapping produced by a HEFT variant. Outline. The rest of the paper is organized as follows. Section 2 surveys related work. In Section 3, we detail our model and discuss complexity results. We introduce new carbon-aware mapping and scheduling algorithms in Section 4 and assess their performance through an extensive set of simulations in Section 5. Finally, we give concluding remarks and hints for future work in Section 6.
2
Related Work
Carbon-aware computing has gained notable attention since datacenters represent a significant share of global carbon emissions and data volumes continue to rise. The current rise of AI and the associated scaling of datacenters adds massively to this effect. Companies such as Meta are already exploring ways to run their hyperscaled datacenters carbon-neutrally [31]. Cao et al. [7] first analyze the carbon footprint of datacenters and corresponding trends and then discuss ways to mitigate the trend of rising carbon footprints by datacenters. In general, much prior work maintains a high-level workload view and does not address the scheduling of workflows (with notable exceptions described later). For example, carbon-aware load balancing for geo-distributed datacenters shifts load to regions with lower carbon intensity, but considers only abstract workloads rather than interdependent tasks [19]. Likewise, cloud providers with globally distributed datacenters shift workloads in a scheduler-agnostic manner to greener sites based on renewable-energy forecasts [22]. However, as Wiesner et al. [30] demonstrate, shifting tasks to periods with cleaner energy is also an efficient approach to save carbon emissions. Breukelman et al. [6] follow a similar abstraction without interdependencies between the jobs and are thus incomparable to our work. Mencaroni et al. [20] present a carbon-aware scheduling approach for flow-shop scheduling. Their model is formulated as a mixed-integer linear program. They solve the problem using a memetic algorithm with notable decrease in carbon emissions and limited effects on the makespan. However, due to the missing precedence constraints, the model is not comparable to our work. Another approach to a model without precedence constraints is the work of Wang et al. [29]. They present a multi-objective scheduling approach where 3
they use reinforcement learning to compute schedules with low carbon emissions and high Quality of Service. Moreover, Hanafy et al. [14] use the elasticity of cloud workloads by adjusting workloads to the carbon intensity. We move on by mentioning some general work regarding workflow scheduling. Since we present a plan-based (offline) approach for scheduling, we focus on these types of algorithms. Note that there is also literature for online scheduling approaches. For this and more literature review, we refer the reader to surveys such as [18]. It is well-known that plan-based scheduling is NP-hard in general [13]. This motivates the use of heuristics for larger problems. There are mainly two different approaches to plan-based scheduling. Partitioning-based approaches partition the input workflow into blocks and assign whole blocks to processors, trading per-task flexibility for scalability [16, 21, 28]. More closely to our work are list-based approaches. One of the most influential examples is HEFT [27]. Since we also use a variation of HEFT in this work, we briefly mention the main idea. In the first phase, HEFT assigns priorities to all tasks. Then, in phase two, it finds suitable assignments for the tasks in that order. The popularity of this approach can be seen in its various extensions such as [5, 24, 26]. In terms of energy and carbon-awareness, there are also adaptations of HEFT to save energy [10, 11]. However, these works do not consider a varying carbon intensity, and hence we cannot compare to them. There is a noteworthy approach by Lechowicz et al. [17] that handles the time-varying availability of greener energy and the precedence constraints between tasks. In particular, they identify structurally important tasks to reduce effects on the makespan. However, there are several severe differences to our framework, among them the carbon cost model, no explicit communication, and the absence of a cluster power model. The carbon-aware workflow scheduling framework CaWoSched [25] is the closest related work. It takes a given mapping as input, i. e., an assignment of tasks to processors, as well as the order of tasks and communications. The input also includes a power profile, which specifies a time horizon ending at the schedule deadline, partitioned into intervals, where each interval has a constant green power budget. Several variants of CaWoSched optimize the schedule in terms of carbon cost by shifting tasks and communications to intervals with a high green power budget. CaWoSched also uses a local search approach to further improve the solution. The main difference with this work is that the mapping and ordering are given in [25], while we aim at determining carbon-effective mappings here, which requires substantially more involved algorithmic components.
3
Framework
The goal is to map and schedule a workflow application, which is a set of interdependent tasks with precedence constraints, onto a parallel platform with a budget of green power that varies with time, in order to minimize the carbon cost. We first describe the application and platform, before defining mappings and schedules. Then, we state the objective function and discuss problem complexity.
4
Application and platform. The workflow application is modeled as a directed acyclic graph (DAG), where the vertices (set V ) represent the tasks, and the edges (set E) express the precedence constraints. The workflow is actually a weighted DAG G = (V, E, ω, c), where ω(v) is the amount of work required by task v ∈ V , and c(vi , vj ) is the amount of data to be communicated if tasks vi and vj are executed on two distinct processors (with (vi , vj ) ∈ E). The goal is to map and schedule the application onto a set of P heterogeneous processors interconnected by homogeneous full-duplex communication links. For 1 ≤ k ≤ P , processor pk has a speed s(pk ) and it can execute task vi ∈ V within i) time ω(v s(pk ) . Mappings and schedules. The mapping µ specifies the processor µ(vi ) on which each task vi ∈ V is executed. Given the mapping, task vi takes time ω(vi ) t(vi ) = s(µ(v to execute. We further define a schedule σ, which specifies the i )) time at which each task is processed, and each communication is initiated. In order to neatly integrate communication costs, similarly to [25], we consider communications as additional tasks to be executed on communication channels. The task corresponding to edge (vi , vj ) ∈ E is denoted by vi,j . There are P (P − 1) communication channels between processors, and we assume that they can be used simultaneously. However, two communications occurring on the same channel must be serialized. For task vi,j , if µ(vi ) ̸= µ(vj ), a communication must occur between both processors, and hence vi,j is mapped onto the corresponding communication channel (between µ(vi ) and µ(vj )), with a speed of β (the platform’s bandwidth). The communication then takes time c(v ,v ) t(vi,j ) = iβ j and we set β = 1 for simplicity. Otherwise, vi,j is mapped onto the processor executing both vi and vj , and its cost is then set to 0, since no communication is required. A schedule σ is valid if each processor never executes more than one task at a time, and all precedence constraints are respected. Formally: (i) σ(v) ≥ 0 for all v ∈ V ; (ii) no overlaps: for all v, v ′ ∈ V with µ(v) = µ(v ′ ), σ(v)+t(v) ≤ σ(v ′ ) or σ(v ′ ) + t(v ′ ) ≤ σ(v); (iii) for (vi , vj ) ∈ E with µ(vi ) = µ(vj ), σ(vi ) + t(vi ) ≤ σ(vj ); and (iv) for (vi , vj ) ∈ E with µ(vi ) ̸= µ(vj ), σ(vi ) + t(vi ) ≤ σ(vi,j ) and σ(vi,j ) + t(vi,j ) ≤ σ(vj ). Objective function. The objective function is to find a valid mapping and schedule in order to minimize the carbon cost, while not exceeding a bound D on the makespan, which is the total execution time: maxv∈V {σ(v) + t(v)} ≤ D. As stated in the introduction, we consider that carbon intensity varies with time, since the amount of available green power depends on many factors. We follow here the notation of our previous work and competitor CaWoSched [25]. Hence, we consider a time horizon [0, T [ divided into J constant-budget intervals PJ Ij = [bj , ej [, 1 ≤ j ≤ J, with j=1 (ej − bj ) = T and green power budget Gj for each time unit t ∈ Ij . Note that D ≤ T . There are a total of P + P (P − 1) = P 2 processors in the system, when accounting for communication channels, and each of them consumes a different amount of static and dynamic power. Let P be the set of processors. Processor
5
p p ∈ P always consumes a static idle power Pidle , and it consumes an additional p power Pwork when executing a task (dynamic power). If the power consumed by all processors at time t ∈ Ij is below Gj , then the carbon cost is zero. Otherwise, the platform must use carbon-emitting power for the excess power, hence incurring a carbon cost of Pt − Gj , where Pt is the sum of all processor power consumptions at time t. The total carbon cost is obtained by integrating over time (0 ≤ t < D).
Problem complexity. In [25], we proved that the decision problem with independent tasks (hence, no communication) that are already mapped and ordered on a set of homogeneous processors (identical speeds, power consumpp p tion values Pidle = 0 and Pwork = 1 for each p ∈ P) is strongly NP-complete. The problem obviously remains strongly NP-complete when we further have to decide the mapping and scheduling. But the problem instance with a single processor – while having polynomial complexity with a fixed mapping and ordering [25] – now becomes strongly NP-complete due to the additional complexity of having to decide the ordering of the tasks. Further, we find that there is no constant-factor approximation, unless P=NP (even when the workflow DAG has no edges): Theorem 3.1. The decision problem of whether there is a mapping and scheduling of a set of independent tasks on a single processor in order to minimize the carbon cost, while not exceeding a bound T on the makespan, with carbon cost not exceeding a given bound C, is NP-complete in the strong sense. Furthermore, there is no polynomial-time λ-approximation algorithm (with λ ≥ 0) such that the algorithm gives a solution with carbon cost CC ≤ λ · CC ∗ , where CC ∗ is the optimal carbon cost, unless P = N P . As a direct consequence, the general problem tackled in this work does not have any constant-factor approximation. The proof of the theorem can be found in Appendix A.
4
Algorithms
In this section, we present a novel algorithm, CWM, for the problem described in Section 3. CWM takes as input (i) a DAG G = (V, E, ω, c) representing the workflow and a user-defined deadline, (ii) cluster specifications such as Pidle , Pwork and the speed s(·) of each processor in the cluster, and (iii) a power profile with a green power budget per interval. From that, CWM computes in two phases a carbon-optimized schedule that meets the deadline. First, it computes a deadline-agnostic preliminary schedule by focusing on making mapping decisions in a carbon-aware way, see Section 4.1. In the second phase, CWM adjusts the schedule so that it meets the deadline (if needed), while still taking carbon costs into account, see Section 4.2. At the end of each phase, we use a local search, described in Section 4.3, to further improve the solution.
6
4.1
Deadline-Agnostic Mapping
The overall idea for computing a carbon-optimized, deadline-agnostic schedule in CWM is the following. For each given interval, we have a power budget. Since the availability of green power varies over time, it is likely that there is not enough green power for the whole cluster to be active at zero cost (at least not all the time). Hence, we solve for every interval a dynamic program to find a suitable subset of processors that can be active at the same time without exceeding the power budget. Within this subset of processors, we then use a version of the list-based scheduling heuristic HEFT [27] to optimize for makespan. The adaptation, which we call HEFT-SL, is necessary to account for the carbon cost of communications. Overall, our approach combines at every stage carbon awareness and deadline awareness. Yet, in this phase, CWM prioritizes carbon awareness for its decisions. First, it chooses for every interval Ij a subset Pj of active computation processors at zero carbon cost as follows. Processor selection. To choose a processor subset Pj for an interval Ij with green power budget Gj , we solve an optimization problem to select a subset of processors that maximizes the combined processor speed while respecting the given green power budget. This is formulated as a variant of the 0 − 1 knapsack problem where items are the available computation processors whose weight is Pwork , the value is the speed s(·) of the processor, and the knapsack capacity is given by max{0, τ (Gj − Pbase )}. The base power Pbase is given by PP 2 i Pbase = i=1 Pidle . To solve the corresponding dynamic program, we use a dynamic programming (DP) table and reconstruct the solution by backtracking through the table. If the capacity is 0 (base power larger than green power budget), we choose Pj = {pmin }, where pmin is one of the processors with pmin pk the smallest dynamic power consumption: Pwork = min1≤k≤P Pwork . This is to ensure that potential bottleneck tasks in the workflow can still be scheduled even if there is not much green power available. Thereby, and by choosing the fastest processor subsets, we incorporate some deadline-awareness in this phase. The parameter τ ≤ 1 buffers against tasks that cross interval boundaries, preventing budget overruns when there are more processors active than planned for the subsequent interval the tasks run into. An example is shown in Appendix B.1, Figure 3. Overall, we obtain a map P_ : {I1 , . . . , IJ } −→ {P1 , . . . , PJ }, where Pj is the chosen processor subset for interval Ij . We also provide pseudocode for this phase in Appendix B.3, Algorithm 1. Initial Mapping and Scheduling. First, CWM ranks the tasks in the workflow using a similar definition as the bottom levels in HEFT [27], i. e., we compute for every task v ∈ V : rank(v) = rt(v) + max(v,w)∈E (c(v, w) + rank(w)), where rt(v) is the mean running time of task v in the cluster. Afterwards, we sort the tasks according to their rank in descending order. To break ties between vertices with the same upward rank, we shuffle the tasks randomly before sorting. Then, the algorithm iterates over the vertices in the order given by the bottom levels. Let v ∈ V be the current task. First, we have to determine which (preliminary) interval to use. For this, we look at the earliest start time of v,
7
ignoring communication: EST′ (v) = max(u,v)∈E (σ(u) + t(u)). Afterwards, we find the interval [bj , ej ) = Ij ∈ {I1 , . . . , IJ }, such that bj ≤ EST′ (v) < ej . (We ignore the communication in this step since we would first have to find suitable spots for the messages – which would be time-consuming.) Then, CWM tries to find an assignment for task v using the processor subset Pj . For this, we follow a HEFT [27]-like procedure and iterate over each processor p ∈ Pj . For each of these processors, we first look at the input arrivals Avp of each predecessor u of v. If µ(u) = µ(v), no communication is necessary and hence we add the finish time of u to the arrivals, i. e., Avp = Avp ∪ {σ(u) + t(u)}. If u and v are on different processors, we must find a valid slot on the link p(µ(u),µ(v)) ; since links are serialized, we tentatively schedule each message to obtain its true earliest arrival time. Note that we cannot just look at the maximum finish time for each predecessor message since this might cause overlaps. An example for such a situation is shown in Appendix B.1, Figure 4. To solve this challenge, we introduce copies of the actual communication links that we only create on demand. Otherwise, the link copies only exist as references to avoid unnecessary copies of the O(P 2 ) communication links. On these link copies, we then actually schedule the communications to find valid spots for them. Once we found the spot for the communication cu,v = (u, v) ∈ E, we add the finish time to the arrivals, i.e., Avp = Avp ∪ {σ(cu,v ) + t(cu,v )}. The order in which we schedule the messages is just the order in which we store them in memory. Once we have gathered all arrivals for the predecessors of v, we have the real earliest start time EST(v) = max(u,v)∈E (σ(cu,v ) + t(cu,v )) = maxt∈Avp (t), where σ(cu,v ) + t(cu,v ) = σ(u) + t(u) if µ(u) = µ(v). To restore the best decision later on without recomputing the communication spots, we store all the data transfers for this processor candidate. Now that we have the earliest start time for v, we can find a spot for the task on the corresponding processor. For this, we look at the earliest gap on the processor that fits the task and respects EST(v). In [27], this is called insertion-based strategy; it yields the earliest finish time EFTp (v) of task v on processor p. The processor pv on which v is scheduled is then simply given by the processor that minimizes EF Tp (v) over all candidate processors in Pj . Ties for EF Tp (v) are broken uniformly at random. Now, we have a preliminary start time σ(v)′ and a preliminary processor assignment p′ for task v. Note, however, that we ignored the communications for the processor subset selection. That is why we check whether the preliminary start time is indeed in the corresponding interval Ij , i.e., we check if bj ≤ σ(v)′ < ej . If not, we look at the next interval Ij+1 and the corresponding processor subset Pj+1 . Then, we repeat the same procedure as for interval Ij , with the additional restriction that the task is not allowed to start earlier than bj+1 . This procedure is repeated at most three times or until we reach the end of the simulated time horizon. Preliminary experiments with other numbers of repetitions yielded no improvements. After that, we just accept the solution found to limit the necessary running time for scheduling and its resulting makespan. At the end of this routine, we have a preliminary schedule, which is subsequently refined with a local search described in Section 4.3. Pseudocode for this procedure can be found in Appendix B.3, 8
Algorithm 2.
4.2
Deadline Repair
In this section, we describe what we do if the initial schedule does not meet the given deadline D. The intuition behind this routine is the following. When restricting the usable processors in the previous step, we limited the parallelism in the workflow. Even though we still aimed for a short makespan, this might have led to deadline violations. Hence, we now try to increase parallelism in the schedule by lifting the constraints on the processor subsets. First, we re-rank tasks as in Section 4.1. In order to compute the set of tasks that we want to reschedule, we look at all tasks v that finish after a given threshold ξ, i.e., σ(v) + t(v) > ξ, and add them to a set R′ . Additionally, we iterate over each task v ∈ R′ and add all its successors to R′ via depth-first search. This is necessary because rescheduling a task might influence its successor tasks. Hence, the set of tasks that we want to reschedule is given by R = {u ∈ V | ∃ v ∈ R′ such that ∃ path v → u}. This set of tasks is rescheduled now without any restrictions on the set of processors, i. e., we use HEFT-SL. Here, we use the order of the tasks given by the ranking that we computed at the beginning of the routine. Furthermore, we respect the assignments of all tasks V \ R and combine the schedules. In the first iteration of this routine, we set ξ = D. If this is not sufficient to reach the deadline, we do a binary search over the deadline from 0 to D, to find the largest threshold ξ such that the deadline is met. Note that if ξ = 0, this is essentially HEFT-SL, which is our fallback solution. Therefore, the deadline that is achievable by HEFT-SL (with the given random seed for tie-breaking) is the tightest deadline that CWM can achieve. If we meet the deadline, we additionally apply the local search algorithm described in Section 4.3. We provide pseudocode for this procedure in Appendix B.3, Algorithms 4,5.
4.3
Local Search
The local search routine further refines the solution, once after the initial scheduling (see Section 4.1), and once more after the deadline repair (see Section 4.2). We identify intervals where we use carbon-emitting power and try to shift tasks from such intervals to other ones. The local search routine runs in several rounds; a parameter ϕ defines the maximum number of iterations. In each iteration, we identify the leftmost interval I where we exceed the green power budget. From this interval, we shift a randomly selected task v ′ together with all its successors, later-scheduled tasks and corresponding communications by the minimal offset required to place v ′ beyond I, while respecting the given deadline D. For a more detailed description of this routine, we refer to Appendix B.2; for pseudocode, we refer to Appendix B.3, Algorithm 3.
9
Table 1: Experimental setup summary. M : makespan computed by HEFT-SL. Parameter / Input Nodes (6 spec types) Number of Workflows Workflow sizes Workflows Profiles Interval lengths Deadlines D τ (processor selection) ϕ (local search) Bandwidth β Total instances
5
Small cluster 6 × 12 = 72
Large cluster 6 × 24 = 144
44 12–30 000 atacseq, bacass, methylseq, eager, chipseq [4, 8] Germany 2024, California 2024 [12], hourly [10, 50] time units α × M for α ∈ {1.2, 1.5, 2.0} 0.8 0.6 500 1 2 × 44 × 2 × 3 = 528
Experimental Evaluation
We evaluate the proposed scheduling algorithm CWM with an extensive set of simulation experiments against multiple competitors. To this end, we adapted HEFT [27] to our communication model; we denote the resulting carbon-agnostic algorithm by HEFT-SL. For the comparison to the state of the art, we include two configurations of our previous work CaWoSched [25]; it is the only competitor we know of that also optimizes for carbon cost within a comparable framework, even though it further considers that the mapping and ordering is fixed. We hence use the initial mapping produced by HEFT-SL, and the CaWoSched code published at https://github.com/KIT-EAE/CaWoSched. We use the same parameter configuration as the original work [25], details can be found there. Furthermore, we use the variants H-CWS-p and H-CWS-s, where −p and −s represent the base score pressure and slack, respectively. Note that the abbreviations of the algorithm’s names are introduced here for clarity. We implemented all algorithms using C++ and compiled them with g++ (v.13.2.0) -O3. The code used for the simulations is publicly available for reproducibility purposes at https://github.com/KIT-EAE/CWM.git. We provide all compiler options there. The simulations are executed on workstations with CentOS 8, 192 GB RAM, and 2 × 12-Core Intel Xeon 6126 at 3.2 GHz. To manage the experiments, we use the tool simexpal [3].
5.1
Experimental Setup
We follow the setup of [25]: The key parameters are summarized in Table 1. Node power and speed values are derived from real-world SPEC benchmarks1 . Communication link powers are drawn from a normal distribution with much 1 From https://www.spec.org/power_ssj2008/results/res2025q1/ as of December 2025: Average Active Power at 100% load for Pwork , at idle for Pidle , and ssj_ops/10000 for s.
10
Figure 1: Performance profile (left) and absolute execution time in seconds (right) for deadline D = 1.5 × M . smaller power values [1]. DAG weights are sampled from a normal distribution, where mean and standard deviation are derived from the speed values of the cluster. For more details on how we obtained these DAGs, we refer to Appendix C. The carbon intensities are inverted and linearly rescaled to a cluster-specific power interval [Pmin , Pmax ] (see Appendix C). Furthermore, we exclude the case α = 1, since CaWoSched uses a specific way of ordering communications and may not obtain a schedule respecting the deadline D = M , and tighter deadlines inherently limit carbon savings.
5.2
Results
We mainly focus on the carbon cost of the schedules produced by each algorithm, since all schedules respect the target deadline. Also, we analyze the time used by the algorithms to compute the schedules and we discuss the trade-off between carbon cost and time. Algorithm Ranking. To rank the different algorithms in terms of carbon cost, we use performance profiles, following the Dolan-Moré methodology [9]. Given an instance i and an algorithm A ∈ {CWM, H-CWS-p, H-CWS-s, HEFT-SL}, we compute its carbon cost CCi,A and we define ri,A := (CCi,A + 1)/(CCi∗ + 1), where CCi∗ is the best cost found for instance i. Note that costs are shifted by +1 to avoid division by zero. We report both geometric means and medians, as the latter are more robust to this shift. Additionally, note that the absolute carbon costs have high values, so that adding 1 is often negligible if both algorithms compute schedules with positive carbon costs. We then plot performance profiles ρA (τ ) = N1 |{i | ri,A ≤ τ }| for varying τ . In this section, we group the instances by the deadline D. A more detailed parameter study is provided later in this section. First, we look at the performance profile for the deadline D = 1.5 × M (left) in Figure 1. Since the CWM curve is consistently at the top, our algorithm performs best. In particular, note that the best found solution is computed by CWM in ≈ 91.48% of the instances. Furthermore, in accordance with the experimental results in [25], we see that H-CWS-s and H-CWS-p perform similarly – with H-CWS-s slightly better. As expected, the carbon-agnostic baseline HEFT-SL yields the
11
Figure 2: Carbon cost ratios compared to CWM for deadlines D = 1.2 × M (left) and D = 2.0 × M (right). worst quality. For a tighter deadline, CWM, H-CWS-s, and H-CWS-p are closer to each other, while with a larger flexibility in the deadline, the dominance of CWM becomes even clearer, see Appendix D. This is to be expected, since there is less / more flexibility for the algorithms to optimize. Carbon cost analysis. To quantify the findings from the algorithm ranking, we look at cost ratios when we compare CWM against the competitors. For an algorithm A ∈ {H-CWS-s, H-CWS-p, HEFT-SL} and an instance i, we look at the carbon cost ratio (CCi,CWM + 1)/(CCi,A + 1). We show the cost ratios for the deadline D = 1.2 × M in Figure 2 (left). There are several instances for which CWM significantly improves over the other algorithms. This can also be seen by the geometric means (numbers are stated in the legend), which weighs the significant improvements more heavily. At the same time, the median improvement by CWM over H-CWS-s and H-CWS-p is rather small (while improvements over HEFT-SL are already noteworthy). With higher flexibility, we see significant improvements also for the median, see Figure 2 (right). Compared to H-CWS-p and H-CWS-s, we almost halve the median carbon cost (48% and 42% decrease, respectively). Note that there are numerous instances for which CWM computes an optimal solution, while the others yield a non-zero carbon cost. In these cases, the geometric mean is less meaningful than the median. Time analysis. To briefly analyze the time the algorithms take to compute the schedules, Figure 1 (right) displays the total running time in seconds for the deadline D = 1.5 × M . For a fair comparison, the running times of H-CWS-p and H-CWS-s include the time for computing an initial mapping with HEFT-SL. For this deadline, CWM is roughly 2× slower than the CaWoSched algorithms and more than 6× slower than HEFT-SL. This is to be expected since HEFT-SL is carbon-agnostic and H-CWS-s and H-CWS-p only shift tasks within a given mapping. Moreover, note that CWM has to apply the repair routine of Section 4.2 more often for a tighter deadline than for larger deadlines. Hence, for D = 2.0 × M , since the costly deadline repair does not have to be used, CWM is about as fast as H-CWS-s and H-CWS-p (see Appendix D), while CWM achieves much better carbon cost values in this case. Parameter study.
Additional plots for all parameter influences are in Ap12
pendix D. In summary: (i) the quality gains of CWM over its competitors is confirmed by results for additional deadlines, i.e., CWM improves the competitors with more deadline flexibility, see Appendix D, Figures 5,6,8; (ii) the difference in running time becomes smaller with more flexibility, see Appendix D, Figure 7; (iii) CWM benefits more from a larger cluster, finding more often solutions of carbon cost zero, especially at D = 2.0 × M , see Appendix D, Figure 9; (iv) the two power profiles (Germany, California) yield similar relative rankings, with CWM finding more solutions of carbon cost zero on the Germany profile, see Appendix D, Figure 10; and (v) CWM’s advantage grows with workflow size, from negligible gains on tiny workflows (≤ 60 tasks) to clearly superior performance on large ones (≈ 20000–30000 tasks), see Appendix D, Figure 11.
6
Conclusion
We have presented a scheduling approach that takes carbon-aware decisions in both the mapping and scheduling phases, while respecting a user-defined deadline. The scheduler restricts the parallelism in the cluster depending on the availability of green power, while it can also lift these constraints to find schedules that respect the deadline. We also provide a local search approach that is capable of further improving the solution. Experiments show that the proposed CWM algorithm clearly dominates state-of-the-art solutions when there is sufficient deadline flexibility. For example, for the largest level of flexibility, we improve CaWoSched by decreasing their carbon cost by 42% and 48%, respectively, depending on the configuration of their setup. This means that we nearly halve the carbon cost in this setting. Compared to the carbon-agnostic baseline, we are able to decrease the carbon cost by 69%. Future work includes adapting the algorithm to an online setting, handling uncertainty in task running times and green power budget, and exploring processor shutdown strategies when suitable schedule slack and power constraints are given – the latter requiring an updated model and novel algorithms. Acknowledgments. This work is partially supported by Collaborative Research Center (CRC) 1404 FONDA – Foundations of Workflows for Large-Scale Scientific Data Analysis, which is funded by German Research Foundation (DFG). The authors designed and implemented the algorithms and wrote the text; they used AI-based tools (GitHub Copilot, ChatGPT, Claude) to support this process.
References [1] Abts, D., Marty, M.R., Wells, P.M., Klausler, P., Liu, H.: Energy proportional datacenter networks. SIGARCH Comput. Archit. News 38(3), 338–347 (Jun 2010) [2] Ahmed, K.M.U., Bollen, M.H.J., Alvarez, M.: A review of data centers energy consumption and reliability modeling. IEEE Access 9 (2021)
13
[3] Angriman, E., van der Grinten, A., von Looz, M., Meyerhenke, H., Nöllenburg, M., Predari, M., Tzovas, C.: Guidelines for experimental algorithmics: A case study in network analysis. Algorithms 12(7), 127 (2019) [4] Bader, J., Lehmann, F., Thamsen, L., Leser, U., Kao, O.: Lotaru: Locally predicting workflow task runtimes for resource management on heterogeneous infrastructures. Future Generation Computer Systems 150, 171–185 (2024) [5] Barbosa, J.G., Moreira, B.: Dynamic scheduling of a batch of parallel task jobs on heterogeneous clusters. Par. computing 37(8) (2011) [6] Breukelman, E., Hall, S., Belgioioso, G., Dörfler, F.: Carbon-aware computing in a network of data centers: A hierarchical game-theoretic approach. In: Europ. Control Conf. (ECC). pp. 798–803. IEEE (2024) [7] Cao, Z., Zhou, X., Hu, H., Wang, Z., Wen, Y.: Toward a systematic survey for carbon neutral data centers. IEEE Comm. Surveys & Tutorials 24, 1–1 (01 2022) [8] Coleman, T., Casanova, H., Pottier, L., Kaushik, M., Deelman, E., Ferreira da Silva, R.: WfCommons: A framework for enabling scientific workflow research and development. Future Generation Computer Systems 128, 16– 27 (2022) [9] Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91(2), 201–213 (2002) [10] Durillo, J.J., Nae, V., Prodan, R.: Multi-objective energy-efficient workflow scheduling using list-based heuristics. Future Generation Computer Systems 36, 221–236 (Jul 2014) [11] Durillo, J.J., Prodan, R., Barbosa, J.G.: Pareto tradeoff scheduling of workflows on federated commercial Clouds. Simulation Modelling Practice and Theory 58, 95–111 (Nov 2015) [12] Electricity Maps: Electricity Maps: Hourly carbon intensity datasets. https://app.electricitymaps.com/datasets (2025), accessed: December 2025 [13] Garey, M.R., Johnson, D.S.: Computers and Intractability, a Guide to the Theory of NP-Completeness. W.H. Freeman and Company (1979) [14] Hanafy, W.A., Liang, Q., Bashir, N., Irwin, D., Shenoy, P.: CarbonScaler: Leveraging Cloud Workload Elasticity for Optimizing Carbon-Efficiency. Proc. ACM Meas. Anal. Comput. Syst. 7(3) (Dec 2023) [15] Haque, M.A., Aydin, H., Zhu, D.: On reliability management of energyaware real-time systems through task replication. IEEE Trans. on Par. and Dist. Systems 28(3), 813–825 (2017) 14
[16] Kulagina, S., Meyerhenke, H., Benoit, A.: Mapping large memoryconstrained workflows onto heterogeneous platforms. In: 53rd Int. Conf. on Par. Processing (ICPP) (2024) [17] Lechowicz, A., Shenoy, R., Bashir, N., Hajiesmaili, M., Wierman, A., Delimitrou, C.: Carbon- and precedence-aware scheduling for data processing clusters. In: Proc. SIGCOMM 2025 Conference. p. 1241–1244. ACM (2025) [18] Liu, J., Lu, S., Che, D.: A survey of modern scientific workflow scheduling algorithms and systems in the era of big data. In: 2020 IEEE Int. Conf. on Services Computing (SCC). pp. 132–141. IEEE (2020) [19] Mahmud, A.H., Iyengar, S.S.: A distributed framework for carbon and cost aware geographical job scheduling in a hybrid data center infrastructure. In: 2016 IEEE Int. Conf. on Autonomic Comp. (ICAC). pp. 75–84 (2016) [20] Mencaroni, A., Leyman, P., Raa, B., De Vuyst, S., Claeys, D.: Towards net-zero manufacturing: Carbon-aware scheduling for GHG emissions reduction. Journal of Cleaner Production 529, 146787 (2025) [21] Özkaya, M.Y., Benoit, A., Uçar, B., Herrmann, J., Çatalyürek, Ü.V.: A scalable clustering-based task scheduler for homogeneous processors using DAG partitioning. In: IEEE Intl. Par. and Distrib. Proc. Symp. (IPDPS). pp. 155–165. IEEE (2019) [22] Radovanović, A., Koningstein, R., Schneider, I., Chen, B., Duarte, A., Roy, B., Xiao, D., Haridasan, M., Hung, P., et al.: Carbon-aware computing for datacenters. IEEE Trans. on Power Sys. 38(2) (2022) [23] Rizvandi, N.B., Zomaya, A.Y., Lee, Y.C., Boloori, A.J., Taheri, J.: Multiple frequency selection in DVFS-enabled processors to minimize energy consumption. Energy-Efficient Dist. Comp. Systems pp. 443–463 (2012) [24] Samadi, Y., Zbakh, M., Tadonki, C.: E-HEFT: Enhancement Heterogeneous Earliest Finish Time algorithm for Task Scheduling based on Load Balancing in Cloud Computing. In: 2018 Int. Conf. on High Perf. Comp. & Simulation (HPCS). pp. 601–609 (2018) [25] Schweisgut, D., Benoit, A., Robert, Y., Meyerhenke, H.: Carbon-aware workflow scheduling with fixed mapping and deadline constraint. In: Proc. of the 54th Int. Conf. on Par. Proc., ICPP 2025. pp. 627–637. ACM (2025) [26] Shi, Z., Dongarra, J.J.: Scheduling workflow applications on processors with different capabilities. Future Gen. Comp. Sys. 22(6) (2006) [27] Topcuoglu, H., Hariri, S., Wu, M.Y.: Performance-effective and lowcomplexity task scheduling for heterogeneous computing. IEEE Trans. Par. Dist. Systems 13(3), 260–274 (2002)
15
[28] Viil, J., Srirama, S.N.: Framework for automated partitioning and execution of scientific workflows in the cloud. The J. of Supercomputing 74, 2656–2683 (2018) [29] Wang, Y., Sun, W., Ren, P., Harrison, G.: Multi-objective low-carbon scheduling method for data centers based on ensemble reinforcement learning. IEEE Trans. on Smart Grid pp. 1–1 (2025) [30] Wiesner, P., Behnke, I., Scheinert, D., Gontarska, K., Thamsen, L.: Let’s wait awhile: how temporal workload shifting can reduce carbon emissions in the cloud. In: Proc. 22nd Int. Middleware Conf. p. 260–272. ACM (2021) [31] Wu, C.J., Raghavendra, R., Gupta, U., Acun, B., Ardalani, N., Maeng, K., Chang, G., et al.: Sustainable AI: Environmental Implications, Challenges and Opportunities (2022), https://arxiv.org/abs/2111.00364
A
Proof of Theorem 3.1
Proof. The (decision version of the) problem obviously is in NP: given a schedule (all tasks are mapped onto the same processor) and a bound on carbon cost, it is easy to check in polynomial time that all constraints are respected, and that the carbon cost does not exceed the bound. The NP-hardness is obtained with a reduction from 3-partition [13]: given an instance of 3-partition with 3n positive integers ai of total sum nB, we build an instance with 3n tasks of duration ai and a single unit-speed processor with a power profile consisting of n intervals of size B having a green power budget of 1, separated by n−1 intervals of size 1 and green power budget 0. The goal is to find a solution of carbon cost 0. There is a clear equivalence between the two problems, since the only way to achieve such a solution is to have a 3-partition of the independent tasks. Now, assume there is a polynomial-time algorithm A with CC(A) ≤ λ · CC ∗ . Then, if CC ∗ = 0, we have CC(A) = 0. Otherwise, CC ∗ > 0 and CC(A) ≥ CC ∗ > 0. Applying algorithm A on the previous problem instance hence allows us to answer in polynomial time whether there is a 3-partition or not, hence proving P=NP.
16
B
Algorithm Details and Pseudocode
B.1
Additional Figures
Figure 3: For interval I1 , all processors are allowed to be active, while in the second interval I2 , only p1 and p2 should be active. However, the task on p3 finishes in interval I2 . Hence, all three processors are active, potentially violating the given green power budget in I2 .
Figure 4: If we would find for each message the earliest gap on the link and just take the maximum of the finish times, the output of v1 and v2 would be scheduled at the same time.
17
B.2
Local Search Details
At each iteration, we first compute a set of refined intervals that correspond to beginning/end of tasks, as well as the carbon cost in each of these intervals (for details on how to compute the carbon cost efficiently, see [25], Appendix A.1). Then, we iterate over the intervals from left to right. If we find an interval where the total power consumption exceeds the budget, this becomes the interval that we want to resolve. We denote this interval by I = [b, e). If we do not find one, we end the routine since the carbon cost is zero in this case. As already mentioned in Section 4.1 and visualized in Figure 3, one main reason for exceeding the green power budget for a given interval is that some tasks start before the interval but continue running during it, i. e., tasks v with σ(v) < b and σ(v) + t(v) > b. Hence, we look at all tasks that run during this interval: CI = {v ∈ V | σ(v) < e and σ(v) + t(v) > b}. We choose one task v ′ uniformly at random in CI , which we aim at shifting to a later interval to reduce the power consumption in interval I. However, we have to ensure that the shift does not violate the validity of the schedule. We also consider the tasks following v ′ , from the task set, i.e., all tasks that start later than e and all successors of v ′ : L′I = {v ∈ V | σ(v) ≥ e} ∪ {v ∈ V | v ∈ succ(v ′ ) and σ(v) < e}, where succ(v ′ ) is the set of all successors of v ′ . Furthermore, we have to ensure that we do not cause overlaps on the processors after shifting tasks. Hence, we look at every task v ∈ L′I and add all tasks u such that µ(u) = µ(v) and σ(u) ≥ σ(v) + t(v) to a new set LI . We then set LI := LI ∪ L′I . Afterwards, we determine the time units by which we shift tasks. Hence, we look at the minimum move that shifts v ′ outside of the interval I, i. e., sv′ = e − σ(v ′ ). We also have the possibility to incorporate the given deadline D into the local search routine. This becomes important when we refine the solution after the deadline repair step. If this is the case, we first compute the latest ending task in the schedule and denote it by vl . Then, we adapt the move to be sv′ = min{(e − σ(v ′ )), (D − (σ(vl ) + t(vl )))}. To be computationally efficient, the idea is now to shift the whole set of tasks {v ′ }∪LI by the same move sv′ . Additionally, we have to shift the corresponding communications as well. Hence, we look at each outgoing message of each task in {v ′ } ∪ LI and shift the communication by sv′ , too. This way, we avoid an expensive rescheduling of each communication individually. The correctness of this approach is shown through the following Lemma B.1 Lemma B.1. Let s ∈ N and let σ be a valid schedule (see Section 3). Furthermore, let v ′ ∈ V and LI be defined as above. Shifting all tasks in {v ′ } ∪ LI and the corresponding outgoing communications by sv′ transforms σ into another valid schedule σ ′ . 18
Proof. To prove the correctness of a schedule σ, we have to show the following properties: 1. For each v ∈ V and each predecessor u of v such that µ(u) = µ(v) we have σ(u) + t(u) ≤ σ(v). 2. For each v ∈ V and each predecessor u of v such that µ(u) ̸= µ(v) we have σ(u) + t(u) ≤ σ(cu,v ) ≤ σ(cu,v ) + t(cu,v ) ≤ σ(v). 3. There are no overlaps on any processor, i. e., there is no pair of tasks u, v such that µ(u) = µ(v) and σ(u) ≤ σ(v) + t(v) and σ(v) ≤ σ(u)
(B.1)
σ(u) ≤ σ(v) ≤ σ(v) + t(v) ≤ σ(u) + t(u).
(B.2)
or 4. Analogously to Property 3, there are no overlaps on any communication link. Now assume σ, σ ′ as stated in Lemma B.1. We assume that the interval which the local search picked is I = [b, e[. First, we show Property 1). Let v ∈ V . If degin (v) = 0, the task is independent and hence, 1) holds. Now assume degin (v) ≥ 1 and let u ∈ Nin (v) and µ(u) = µ(v), i. e., the tasks are located on the same processor. In σ, we have σ(u) + t(u) ≤ σ(v). Since tasks never get scheduled earlier but only later, we only have to consider the case when u gets shifted. In this case, u is a successor of the task v ′ picked by the local search – or it begins later than e. By design of the local search, v is moved as well in both cases. Hence, we still have σ ′ (u) + t(u) ≤ σ ′ (v), and Property 1) still holds for σ ′ . Now we look at Property (2), i. e., we consider u, v ∈ V with µ(u) ̸= µ(v). In this case, there is a message cu,v from µ(u) to µ(v). Since σ is a valid schedule, we have σ(u) + t(u) ≤ σ(cu,v ) ≤ σ(cu,v ) + t(cu,v ) ≤ σ(v). (B.3) First, note that the message cu,v cannot be moved if u is not moved, by design of the local search. Hence, with the same arguments as above, we only have to look at the case when u is moved. In this case, cu,v is moved as well, since all outgoing messages of the shifted messages are shifted as well. Additionally, by the same arguments as above, because v is a successor of u and starts before e or because v starts later than e, v is moved as well by the same move as u and cu,v . Hence, Eq. (B.3) becomes σ ′ (u) + t(u) + sv′ ≤ σ ′ (cu,v ) + sv′ ≤ σ ′ (cu,v ) + t(cu,v ) + sv′ ≤ σ ′ (v) + sv′ , 19
and the schedule σ ′ remains correct in this case. Next, we show Property 3). Let u, v ∈ V with µ(u) = µ(v) be as in Eq. (B.1). First, since every tasks is moved by the same amount, we can assume that only one task is moved. Without loss of generality, we assume that in S we have σ(u) + t(u) ≤ σ(v), i.e., u is processed before v. First, assume only u is moved. In this case, by design of the local search, all later tasks on µ(u) are moved as well. Hence, this cannot be the case. Since in σ tasks are only moved to later time units, and because u is processed before v in σ, we do not have to look at the case where only v is moved. Hence, our assumption that there are tasks u, v ∈ V that overlap on the same processor is a contradiction. Further, we see that the same arguments hold for u, v ∈ V such that Eq. (B.2) holds. Hence, Property (3) holds. Moreover, since the routines for adding later tasks on a processor or communication link is the same, it follows that Property 4) holds as well by the same arguments. Overall, σ ′ is a valid schedule.
20
B.3
Pseudocode
Algorithm 1 Processor Subset Selection for Interval Ij Input: Green power budget Gj , base power Pbase , processor speeds s(·), dynamic powers Pwork , parameter τ Output: Processor subset Pj 1: C ← max 0, τ (Gj − Pbase ) 2: if C = 0 then p 3: return {pmin } where pmin = arg minp Pwork ▷ tie-breaking by index 4: Solve 0/1 knapsack by dynamic programming (DP), where items = processors, p weight = Pwork , value = s(p), capacity = C 5: Pj ← Reconstruct solution by backtracking through DP table 6: if Pj = ∅ then 7: return {pmin } 8: return Pj
21
Algorithm 2 Deadline-Agnostic Initial Mapping / Schedule Input: DAG G = (V, E, ω, c), intervals {I1 , . . . , IJ }, tuning parameter τ , processors and communication channels, green power budgets (G1 , . . . , GJ ), Pidle , Pwork , processor speeds s(·), maximum number of local search iterations ϕ Output: Preliminary carbon-aware schedule σ 1: for interval Ij ∈ {I1 , . . . , IJ } do 2: Pj ← ProcessorSubset(Gj , Pbase , s(·), Pwork , τ ) ▷ Algorithm 1 3: Compute rank(v) = rt(v) + max(v,w)∈E (c(v, w) + rank(w)) for all v ∈ V 4: π ← Sort V by rank(·) descending (random tie-breaking) 5: for task v ∈ π do 6: EST′ (v) ← max(u,v)∈E σ(u) + t(u) 7: Find Ij = [bj , ej ) s.t. bj ≤ EST′ (v) < ej 8: (pbest , σ(v)′ ) ← FindChoice(v, Pj ) ▷ pick arg min EFT 9: retries ← 0 10: while σ(v)′ ∈ / Ij and retries < 3 and j+1 < J do 11: j ← j + 1; retries ← retries + 1 12: (pbest , σ(v)′ ) ← FindChoice(v, Pj , start not earlier than bj ) 13: µ(v) ← pbest ; σ(v) ← σ(v)′ ; schedule all communications cu,v insertion based 14: Apply LocalSearch(σ, D=∞, ϕ) ▷ Algorithm 3 15: return σ
22
Algorithm 3 Local Search Input: Schedule σ, deadline D, max iterations ϕ, intervals {I1 , . . . , IJ } Output: Refined schedule σ 1: for i = 1 to ϕ do 2: Compute refined intervals by sweep-line over task/communications and interval bounds 3: Find leftmost refined interval I = [b, e) with total power > GI ; 4: if no such interval exists then 5: return 6: CI ← {v ∈ V | σ(v) < e and σ(v) + t(v) > b} ▷ tasks running in I 7: if CI = ∅ then 8: return 9: v ′ ← draw task uniformly at random from CI 10: L′I ← {v ∈ V | σ(v) ≥ e} ∪ {u ∈ succ(v ′ ) | σ(u) < e} 11: for v ∈ L′I do 12: LI ← LI ∪ {u ∈ V | µ(u) = µ(v) and σ(u) ≥ σ(v) + t(v)} 13: LI ← L′I 14: vl ← arg maxu∈{v′ }∪LI σ(u) + t(u) 15: sv′ ← min e − σ(v ′ ), D − (σ(vl ) + t(vl )) 16: if sv′ ≤ 0 then 17: return 18: Shift all tasks in {v ′ } ∪ LI by sv′ 19: Shift all outgoing communications of tasks in {v ′ } ∪ LI by sv′ 20: return σ
23
Algorithm 4 Deadline Repair Input: Schedule σ (from Algorithm 2), deadline D Output: Deadline-feasible schedule σ ′ 1: if makespan(σ) ≤ D then 2: Apply LocalSearch(σ, D) 3: return σ 4: π ← Re-compute upward ranks and sort V by rank descending 5: σ ′ ← Reschedule(σ, ξ=D, π) ▷ Algorithm 5 6: if makespan(σ ′ ) ≤ D then 7: Apply LocalSearch(σ ′ , D) 8: return σ ′ 9: ξlow ← 0; ξhigh ← D 10: while ξlow + 1 < ξhigh do 11: ξmid ← ξlow + ⌊(ξhigh − ξlow )/2⌋ 12: σ ′ ← Reschedule(σ, ξmid , π) ▷ Algorithm 5 13: if makespan(σ ′ ) ≤ D then 14: ξlow ← ξmid 15: else 16: ξhigh ← ξmid 17: σ ′ ← Reschedule(σ, ξlow , π) ▷ Algorithm 5 18: Apply LocalSearch(σ ′ , D) 19: return σ ′
Algorithm 5 Rescheduling Procedure for Deadline Repair Input: Schedule σ, deadline D, threshold ξ Output: Shifted schedule σ ′ 1: R′ ← {v ∈ V | σ(v) + t(v) > ξ} 2: Via DFS: R ← R′ ∪ {u | ∃ v ∈ R′ with path v → u} 3: σ ′ ← Initialize by keeping schedule of V \ R from σ fixed 4: for v ∈ R in order π do 5: Schedule v using HEFT-SL on all processors ▷ no subset restriction 6: return σ ′
24
C
Setup Details
Workflows. In line with Section 3, we represent the workflows as DAGs. To create them, we use the same tools and techniques as in [25]: we first take realworld workflows (atacseq, bacass, methylseq (only a rescaled version is used), eager, chipseq) from [4], transform them to our model, and scale them with the WFGen generator [8] to the desired size. The resulting 44 workflows have between 12 and 30 000 vertices. The DAG weights are sampled from a normal distribution, where mean and standard deviation are derived from the speed values of the cluster. Profiles. For the power budget profiles, we use a more realistic approach than [25]. We sample real carbon intensities from an Electricity Maps dataset [12], using the hourly data for Germany and for California in 2024. A given time horizon is first partitioned into intervals by computing random split points. Thereby, we ensure that each interval length is uniform within a configurable integer range (we chose [10, 50]). For the intervals, we pick a contiguous subsequence of carbon intensity values uniformly at random. Depending on the cluster type, we then rescale the values as follows to invert the carbon intensities, making the smallest carbon intensity correspond to the largest green power budget: For the sequence of values, we denote by [xmin , xmax ] the range of carbon intensities. Then we map this range to a target power interval [Pmin , Pmax ], where we choose Pmin to be the sum of all idle powers in the cluster and for Pmax we add a fraction (0.2 for the small cluster, 0.4 for the large cluster) of the sum of all dynamic power values for the compute nodes and the communication links. Then, any carbon intensity x becomes x′ = Pmax −
x − xmin (Pmax − Pmin ). xmax − xmin
25
(C.1)
D
Additional Experimental Results
In this section, we show additional plots for the experimental evaluation of the algorithms performed in Section 5.
Figure 5: Performance profiles for deadlines D = 1.2×M (left) and D = 2.0×M (right).
Figure 6: Carbon cost ratios as described in Section 5.2 for deadline D = 1.5 × M .
26
Figure 7: Absolute execution time (seconds) for each algorithm for deadlines D = 1.2 × M (left) and D = 2.0 × M (right).
Figure 8: Absolute carbon cost for each algorithm for deadlines D = 1.2 × M (top left), D = 1.5 × M (top right), and D = 2.0 × M (bottom).
27
Figure 9: Carbon cost ratios for each competitor for the small and large cluster and for the deadlines D = 1.5×M and D = 2.0×M . Small cluster, D = 1.5×M : top left; Small cluster, D = 2.0 × M : top right; Large cluster, D = 1.5 × M : bottom left; Large cluster, D = 2.0 × M : bottom right.
Figure 10: Carbon cost ratios for each competitor for the Germany profile (left) and the California profile (right) and the deadline D = 1.5 × M .
28
Figure 11: Carbon cost ratios for each competitor for tiny real-world (≤ 60 tasks, top left), small (≈ 200 − 4000 tasks, top right), medium (≈ 8000 − 15000 tasks, bottom left) and large (≈ 20000 − 30000 tasks, bottom right) workflows and deadline D = 1.5 × M .
29