Large-scale workflows for big data analytics have become a main consumer of energy in data centers where moldable parallel computing models such as MapReduce are widely applied to meet high computational demands with timevarying computing resources. The granularity of task partitioning in each moldable job of such big data workflows has a significant impact on energy efficiency, which remains largely unexplored. In this paper, we analyze the properties of moldable jobs and formulate a workflow mapping problem to minimize the dynamic energy consumption of a given workflow request under a deadline constraint. Since this problem is strongly NP-hard, we design a fully polynomialtime approximation scheme (FPTAS) for a special case with a pipeline-structured workflow on a homogeneous cluster and a heuristic for the generalized problem with an arbitrary workflow on a heterogeneous cluster. The performance superiority of the proposed solution in terms of dynamic energy saving and deadline missing rate is illustrated by extensive simulation results in Hadoop/YARN in comparison with existing algorithms.
Next-generation applications in science, industry, and business domains are producing colossal amounts of data, now frequently termed as “big data”, which must be analyzed in a timely manner for knowledge discovery and technological innovation. Among many practical computing solutions, workflows have been increasingly employed as an important technique for big data analytics, and consequently such big data workflows have become a main consumer of energy in data centers. Most existing efforts on green computing were focused on independent MapReduce jobs and traditional workflows comprised of serial programs. Energy efficiency of big data workflows in Hadoop systems still remains largely unexplored.
Modern computing systems achieve energy saving mainly through two types of techniques, i.e. task consolidation to reduce static energy consumption (SEC) by turning off idle servers, and load balancing to reduce dynamic energy consumption (DEC) through dynamic voltage and frequency scaling (DVFS), or a combination of both. However, these techniques are not sufficient to address the energy efficiency issue of big data workflows because i) frequently switching ∗Copyright held by the author(s). on and off a server may reduce its lifespan or cause unnecessary peaks of energy consumption, and ii) DVFS may not be always available on all servers in a cluster. Therefore, we direct our efforts to workflow mapping for dynamic energy saving by adaptively determining the degree of parallelism in each MapReduce job to mitigate the workload overhead while meeting a given performance requirement.
Parallel jobs are generally categorized into three classes
with flexibility from low to high: rigid jobs exemplified by
multi-threaded programs running on a fixed number of
processors, moldable jobs exemplified by MapReduce programs
running on any number of processors decided prior to
execution, and malleable jobs running on a variable number of
processors at runtime [
The validity of this model has been verified by many reallife parallel programs in various big data domains and will serve as a base of our workflow mapping solution for energy saving of big data workflows.
In this paper, we construct analytical cost models and
formulate a workflow mapping problem to minimize the DEC
of a workflow under deadline and resource constraints in
a Hadoop cluster. This problem is strongly NP-hard
because a subproblem to minimize the makespan of
independent jobs on identical machines under a single resource
constraint without considering energy cost has been proved to
be strongly NP-hard [
We start with a special case with a pipeline-structured
workflow (a set of linearly arranged jobs with a dependency
between any two neighbors along the line) on a
homogeneous cluster. We prove this special case to be weakly
NP-complete and design a fully polynomial-time
approximation scheme (FPTAS) of time complexity linear with
respect to 1/ǫ. By leveraging the near optimality and low
time complexity of our FPTAS, we design a heuristic for the
generalized problem with a directed acyclic graph
(DAG)structured workflow on a heterogeneous cluster. This
heuristic iteratively selects the longest chain of unmapped jobs
from the workflow and applies our FPTAS to the selected
pipeline while taking machine heterogeneity into
consideration.
In sum, our work makes the following contributions to the Hadoop cluster powered by mixed brown and green energy,
field. which dynamically determines resource allocation to
hetero• To the best of our knowledge, our work is among the geneous jobs based on the estimation of job completion time
first to study energy-efficient mapping of big data work- and the prediction of future resource availability [
A large number of research efforts have been made to
optimize the data replication scheme in Hadoop distributed
file system (HDFS) so that data nodes can be turned off
without affecting data availability [
2.1.1 Heterogeneous Computing Environments
Since servers in large-scale clusters are typically upgraded
or replaced in an incremental manner, many techniques con- Other approaches were focused on physical clusters as
sider hardware heterogeneity of Hadoop clusters for energy follows. Lee et al. proposed a static workflow schedule
saving. Cardosa et al. proposed static virtual machine (VM) compaction algorithm to consolidate the resource use of a
placement algorithms to minimize the cumulative machine workflow schedule generated by any scheduling algorithm
uptime of all physical machines (PMs), based on two prin- in homogeneous environments [
Many efforts were made on energy-efficient scheduling of
workflows comprised of precedence-constrained serial
programs. Some of these approaches targeted virtualized
environments by migrating active VMs onto energy-efficient
PMs in time [
Several efforts were focused on utilizing renewable energy
in the operation of Hadoop clusters. Goiri et al. proposed
a framework, GreenHadoop, for a data center powered by
renewable (green) energy and by carbon-intensive (brown)
energy from the electrical grid as a backup. It dynamically
schedules MapReduce jobs to minimize brown energy
consumption by delaying background computations within their
time bounds to match the green energy supply that is not
always available [
Some efforts have been made to minimize the
completion time of a workflow comprised of malleable jobs [
3.1.1 Cluster Model
We consider a heterogeneous Hadoop cluster consisting of a set M of machines connected via high-speed switches, which can be partitioned into homogeneous sub-clusters {Cl}. Each machine mi is equipped with Ni homogeneous CPU cores of speed pi and a shared memory of size oi. For the entire cluster, a central scheduler maintains an available resource-time (ART) table R, which records the number NiA(t) ≤ Ni of idle CPU cores and the size oiA(t) ≤ oi of available memory in each machine mi at time t. 3.1.2 Workflow Model
We consider a user request in the form of a workflow f (G, d), which specifies a workflow structure G and a deadline d. The workflow structure is defined as a DAG G(V, A), where each vertex vj ∈ V represents a component job, and each directed edge aj,j′ ∈ A denotes an execution dependency, i.e. the actual finish time (AFT) tjAF of job vj must not be later than the actual start time (AST) tjA′S of job vj′ . The completion time of the workflow is denoted as tC . We consider the map and reduce phases of each MapReduce job as two component jobs connected via an execution dependency edge. 3.1.3 MapReduce Model
We consider a MapReduce job vj running a set of parallel map (or reduce) tasks, each of which requires a memory of size oj and spends a percentage µ i,j of time executing CPUbound instructions on a CPU core of machine mi. In job vj , generally, as the number Kj of parallel tasks increases, the workload wj,k(Kj ) of each task sj,k decreases and the total workload wj(Kj ) = Kj · wj,k(Kj) of all tasks increases. However, the maximum number Kj′ of tasks that can be executed in parallel without performance degradation is limited by the cluster capacity, e.g. Kj′ ≤ Pmi∈M min{Ni, ⌊oi/oj ⌋}. Note that a serial program can be considered as a special case of a MapReduce job with Kj′ = 1. The execution time of task sj,k on machine mi is ti,j,k = wj,k(Kj)/(µ i,j · pi). Estimating the execution time of a task on any service is an important issue. Many techniques have been proposed such as code analysis, analytical benchmarking/code profiling, and statistical prediction, which are beyond the scope of this work.
The active state ai,j,k(t) of task sj,k on machine mi is 1 (or 0) if it is active (or inactive) at time t. The number of active tasks in job vj on machine mi at time t is ni,j (t) = Psj,k∈vj ai,j,k(t). The number of CPU cores and the size of memory used by all component jobs of a workflow on machine mi at time t are ni(t) = Pvj∈V ni,j (t) and oi(t) = Pvj ∈V [oj ni,j (t)], respectively. 3.1.4 Energy Model
The DEC of a workflow in a cluster is
tC
E = Pmi∈M {Pi Pvj∈V [µ i,j R0 ni,j (t)dt]}, where Pi is the
dynamic power consumption (DPC) of a fully utilized CPU
core, and which is validated by energy measurements of
practical systems in [
We define a workflow mapping function as M : {sk(vj ) [tjS,k, tjE,k] ======⇒ mi, ∀vj ∈ V, ∃mi ∈ M, ∃[tjS,k, tjF,k] ⊂ T }, which denotes that the k-th task of the j-th job is mapped onto the i-th machine from time tjS,k to time tjE,k. The domain of this mapping function covers all possible combinations of a set V of component jobs of the workflow, a set M of machines, and a time period T of workflow execution.
We formulate a deadline- and resource-constrained workflow mapping problem for energy efficiency (EEWM):
Definition 1. EEWM: Given a cluster {mi(Ni, pi, oi, Pi)} of machines with an available resource-time table {NiA(t), oiA(t)}, and a workflow request f (G(V, A), d), where each job vj has ′ a set {wj (Kj)|Kj = 1, 2, . . . , Kj} of workloads for different task partitions, and each task in job vj has a percentage µ i,j of execution time for CPU-bound instructions on machine mi and a memory demand oj , we wish to find a mapping function M : (V, M, T ) → {sk(vj ) =[t=jS=,k=,=tjE=,⇒k] mi} to minimize the dynamic energy consumption: min E,
M subject to the following deadline and resource constraints: tC ≤ d, tjAF ≤ tjA′S, ∀aj,j′ ∈ A, ni(t) ≤ NiA(t), ∀mi ∈ M, oi(t) ≤ oiA(t), ∀mi ∈ M.
We start with a special case with a Pipelined-structured workflow running on HOmogeneous machines (PHO). We prove it to be NP-complete and design an FPTAS to solve EEWM-PHO. Generally, we may achieve more energy savings on an under-utilized cluster than on a fully-utilized cluster. Hence, the problem for a single pipeline-structured workflow is still valuable in real-life systems. The EEWM-PHO problem is defined as follows.
Definition 2. EEWM-PHO: Given I idle homogeneous machines {mi(N, p, o, P )} and a workflow f (G(V, A), d) containing a chain of J jobs, where each job vj has a workload list {wj (Kj)|Kj = 1, 2, . . . , Kj′ }, and each task in job vj has a percentage µ j of execution time for CPU-bound instructions and a memory demand oj , does there exist a feasible mapping scheme such that DEC is no more than E?
We prove that EEWM-PHO is NP-complete by reducing the two-choice knapsack problem (TCKP) to it.
Definition 3. Two-Choice Knapsack: Given J classes of items to pack in a knapsack of capacity H, where each class Cj (j = 1, 2, . . . , J) has two items and each item rj,l (l = 1, 2) has a value bj,l and a weight hj,l, is there a choice of exactly one item from each class such that the total value is no less than B and the total weight does not exceed H?
The knapsack problem is a special case of TCKP when we put each item in the knapsack problem and a dummy item with zero value and zero weight together into a class. Since the knapsack problem is NP-complete, so is TCKP.
Theorem 1. EEWM-PHO is NP-complete.
Proof. Obviously, EEWM-PHO ∈ N P . We prove that EEWM-PHO is NP-hard by reducing TCKP to EEWMPHO. Let ({Cj(bj,1, hj,1, bj,2, hj,2)|1 ≤ j ≤ J}, B, H) be an instance of TCKP. Without loss of generality, we assume that bj,1 > bj,2 and hj,1 > hj,2 > 0. If hj,1 < hj,2, rj,1 would always be selected. If hj,2 = 0, we can always add τ > 0 to hj,1, hj,2 and H such that hj,2 > 0.
We construct an instance of EEWM-PHO as follows. Let I = 2, d = H, vj = Cj, Kj′ = 2, oj = o, wj (1) = hj,1µ j p, wj (2) = 2hj,2µ jp, uj = (Bj −bj,1)/(hj,1P ) and E = P1≤j≤J Bj − B, where Bj = (2hj,2bj,1 − hj,1bj,2)/(2hj,2 − hj,1). It is obvious that the construction process can be done in polynomial time.
Then, if job vj only has one task, its execution time is tj (1) = wj (1)/(µ j p) = hj,1, and its DEC is Ej(1) = tj(1)µ j P = Bj − bj,1. If job vj has two tasks, the execution time of each task is tj (2) = wj (2)/(2µ j p) = hj,2, and the DEC of job vj is Ej(2) = 2tj (2)µ j P = Bj − bj,2. Obviously, two tasks in a job are mapped onto two machines simultaneously.
Therefore, if the answer to the given instance of TCKP is YES (or No), the answer to the constructed instance of EEWM-IJOM is also YES (or No). Proof ends.
We prove that EEWM-PHO is weakly NP-complete and
design an FPTAS as shown in Alg. 1 by reducing this
problem to the weakly NP-complete restricted shortest path (RSP)
problem [
Given an instance of EEWM-PHO, we construct an instance of RSP according to the pipeline-structured workflow as follows. As illustrated in Fig. 1, the network graph G consists of V = {vj,k|j = 1, . . . , J, k = 1, . . . , Kj} ∪ {u0, uj|j = ′ 1, . . . , J} with a source u0 and a destination uJ , and E = {e2j−1,k , e2j,k|j = 1, . . . , J, k = 1, . . . , Kj′ }, where e2j−1,k = (uj−1, vj,k) and e2j,k = (vj,k, uj). Then, we calculate the execution time of job vj with k tasks as tj(k) = wj(k)/(k·p·µ j ),
e1,1 u0 e1,K1’ e1,2 ⁞ e1,k v1,k and accordingly its DEC as Ej(k) = k · P · µ j · tj (k). Subsequently, we assign the cost c(e) and delay l(e) of each edge e ∈ E as c(e2j−1,k) = Ej(k), l(e2j−1,k) = tj(k), and c(e2j,k) = l(e2j,k) = 0, and set the delay constraint on a path from u0 to uJ to be d. As a result, the minimum cost in RSP is exactly the minimum DEC in EEWM-PHO, and if vj,k is on the solution path to RSP, the j-th job has k tasks. Based on Theorem 1 and the above reduction, we have Theorem 2. EEWM-PHO is weakly NP-complete.
Let K′ = max1≤j≤J Kj′ . Then, |V| ≤ JK′ + J + 1 and
|E| ≤ 2JK′ in the constructed graph G. It is obvious that
the construction process can be done within time O(JK′).
Therefore, EEWM-PHO finds a feasible solution that
consumes energy within the least DEC multiplied by (1 + ǫ) in
time O(J2K′2/ǫ) if the FPTAS in [
We consider EEWM with a DAG-structured workflow on a heterogeneous cluster and design a heuristic algorithm, referred to as big-data adaptive workflow mapping for energy efficiency (BAWMEE).
The key idea of BAWMEE is to partition a DAG into a set of pipelines and then repeatedly employ Alg. 1 with near optimality and low time complexity to achieve energyefficient mapping of each pipeline.
In BAWMEE, each workflow mapping consists of two components: iterative critical path (CP) selection and pipeline mapping. A CP is the longest execution path in a workflow, which can be calculated in linear time. The algorithm starts with computing an initial CP according to the average execution time of each job running in serial on all the machines, followed by a pipeline mapping process. Then, it iteratively
Input: a workflow f (G(V, A), d) and an ART table R for sub-clusters {Cl} 1: T bl ← buildT ET (V, {Cl}); 2: if simplyM ap(f, R({Cl}), T bl) =True then 3: return . 4: tjLF ← +∞ for ∀vj ∈ f ; tJLF ← d for the end job vJ in f ; 5: Calculate the average execution time t¯j of each job vj running in serial on all the machines; 6: G′ ← G; 7: while ∃ an unmapped job ∈ V do 8: Find the critical path cp ending at a job v with the earliest LFT in G′ according to {t¯j |vj ∈ G′}; 9: if EEP M (cp, R({Cl}), T bl) =False then 10: v ← M DP M (cp, R({Cl})); 11: if v 6= Null then 12: D ← {all the downstream jobs of v in G − G′}; 13: if D 6= ∅ then 14: Cancel the mapping of each job v′ ∈ D, and add v′ and its associated precedence constraints to G′; 15: EAJM (v, R({Cl}); 16: G′ ← G′ − {vj ∈ cp|vj is mapped}; computes a CP with the earliest last finish time (LFT) from the remaining unmapped workflow branches based on the same average execution time of a job as above and performs a pipeline mapping of the computed CP until there are no branches left.
In pipeline mapping, we consider two extreme scenarios: resource/time sufficiency and resource/time insufficiency. In the former case, we only need to focus on energy efficiency, while in the latter case, it may be unlikely to meet the performance requirement. Therefore, we design one algorithm for each of these two scenarios: a heuristic for energyefficient pipeline mapping (EEPM) under a deadline constraint in Alg. 3, which calls Alg. 1, and a heuristic for minimum delay pipeline mapping (MDPM) with energy awareness in Alg. 4. If Alg. 3 fails to find a feasible mapping scheme due to limited resources, we resort to Alg. 4. In EEPM, due to the homogeneity of tasks in a job, we map all the tasks in the same job onto a homogeneous sub-cluster, hence using Alg. 1 to balance the trade-off between execution time and DEC (directly associated with total workload) for each job on a pipeline. In MDPM, we search for a good task partitioning to minimize the end time of each job through a limited number of tries by reducing the possi′ ble number of tasks in each job vj from {1, 2, 3, . . . , Kj} to ′ {1, 2, 22, . . . , 2⌊log Kj⌋} ∪ {Kj′ }. 5.2
If a job vj has been mapped, it has AST tjAS and AFT tjAF . If all the preceding (and succeeding) jobs, in P rec (and Succ), of job vj are mapped, its earliest start time (EST) (and LFT) can be calculated as tjES = (0, if vj is the start job of workflow f,
max tA′F , otherwise; vj′ ∈P rec(vj) j
Input: a pipeline pl with its EST pl.est and LFT pl.lf t, an
ART table R({Cl}), and TETs {T blj } Output: a boolean variable to indicate whether pl or its part is mapped 1: Label the index j of each job in pl from 1 to the length of pl; 2: Calculate the earliest possible start time of the first job in pl on any machine as est according to R({Cl}); 3: pl.est ← max{est, pl.est}; 4: if Pvj∈pl tj (Kj,1, Cj,1) > pl.lf t − pl.est then 5: return False. 6: Convert pipeline pl, where each quadruple in T blj of each job vj ∈ pl corresponds to one of its mapping options, into a network graph in RSP; 7: Use Alg. 1 to calculate the number Kj of tasks, sub-cluster
C(vj ), and start and finish time, tjS and tjF , for each job vj ; 8: for vj+1 ∈ pl do 9: if tjF > t′LF (vj ) or tjF < t′ES (vj+1) then 10: pl(1, j).est ← pl.est; 11: if tjF > t′LF (vj ) then 12: pl(1, j).lf t ← t′LF (vj ); 13: else 14: pl(1, j).lf t ← min{t′ES (vj+1), t′LF (vj ), pl.lf t}; 15: return EEP M (pl(1, j), R({Cl}), T bl); 16: if ∃ Kj pairs of a CPU core and memory of size oj in
R(C(vj )) for ∀vj ∈ pl then 17: Map all Kj tasks onto C(vj ) from tjS to tjF for ∀vj ∈ pl; 18: return True; 19: return False; and tLF = j (d, if vj is the end job of workflow f, vj′ ∈Succ(vj) tjA′S, otherwise,
min respectively. If there exist unmapped preceding and succeeding jobs of vj , its temporary earliest start time (TEST) t′ES(vj) and temporary last finish time (TLFT) t′LF (vj) can be calculated based on only its mapped preceding and succeeding jobs, respectively. The EST and LFT of a pipeline are the EST of its first job and LFT of its end job, respectively.
Each job vj is associated with a set of pairs of the number Kj,n of tasks and the used homogeneous sub-cluster Cj,n. Each pair corresponds to a certain execution time tj(Kj,n, Cj,n) and DEC ej(Kj,n, Cj,n) = P (Cj,n)wj (Kj,n)/p(Cj,n), where p(Cj,n) and P (Cj,n) are the speed and the DPC of a fully utilized CPU core on a machine in Cj,n, respectively, and wj (Kj,n) is the workload of vj with Kj,n tasks. All the quadruples {(tj (Kj,n, Cj,n), ej(Kj,n, Cj,n), Kj,n, Cj,n)} are sorted in the ascending order of execution time as listed in Table 2, and are referred to as the time-energy table (TET) T blj of job vj . Any quadruple with both execution time and DEC larger (worse) than those of another will be deleted from T blj.
In Alg. 2, BAWMEE first builds a time-energy table for each job by calling buildT ET (). If the workflow cannot meet its deadline with each job running the fastest, BAWMEE performs energy-aware job mapping (EAJM) with minimum finish time for each job in a topologically sorted order by calling simplyM ap(). Otherwise, BAWMEE employs iterative CP selection to find a CP with the earliest LFT from unmapped jobs, and performs EEPM or MDPM (if EEPM fails) for the selected CP. If there is any job that cannot
MDPM Input: a pipeline pl and an ART table R for {Cl} Output: the first job that cannot be mapped 1: for all vj ∈ pl do 2: if EAJM (vj , R({Cl})) > t′LF (vj ) then 3: Cancel the mapping of job vj ; 4: return vj ; 5: return Null.
Input: a job vj and an ART table R for sub-clusters {Cl} Output: the EFT tjEF of job vj 1: Update the TEST t′ES(vj ); tjEF ← +∞; 2: for K ← 1, 2, 4, . . . 2jlog Kj′k, Kj′ do 3: Calculate the EFT tjEF (K) of job vj with K tasks by minimizing the finish time of each task one by one; 4: if tjEF > tjEF (K) then 5: tjEF ← tjEF (K); Kj ← K; 6: Map job vj consisting of Kj tasks until tjEF ; 7: return tjEF . be mapped in MDPM, we cancel the mapping of its downstream jobs. If it is the last job of the workflow, we perform EAJM with minimum finish time.
In Alg. 3 of EEPM, we reset the EST for the input pipeline according to the earliest time such that enough resources are made available to the first job. If the pipeline cannot meet its LFT with each job running the fastest, we exit EEPM; otherwise, the mapping of a pipeline with its EST and LFT is converted into the RSP problem with a relaxed resource limit. Accordingly, we calculate the number of tasks, the sub-cluster, and the start/finish time for each job using Alg. 1. Then, we check if the start and finish time of each job are between its TEST and TLFT in their execution order. If there exists a job that violates the precedence constraint, we divide the pipeline at this job, and use Alg. 3 to compute the mapping of the upstream sub-pipeline with an updated LFT constraint. We repeat this process until we find a sub-pipeline whose mapping meets all precedence constraints. If the cluster is able to provide each job in this sub-pipeline with enough resources based on the mapping result of Alg. 1, we proceed with this mapping; otherwise, we fail to find an EEPM and thus exit. In this case, BAWMEE would proceed to search for an MDPM.
In Alg. 4 of MDPM, we search for the earliest finish time (EFT) of each job using EAJM in their execution order, and thus obtain the EFT of the entire pipeline. In Alg. 5 of EAJM with minimum finish time under resource constraints, we exponentially relax the limit on the maximum number of tasks in a job to make a tradeoff between the optimality and the time complexity of EAJM.
Since EEPM and MDPM are of O(J2K′L[log(K′L) + 1/ǫ] + M ′H) and O(M ′HJK′ log K′), respectively, the time complexity of BAWMEE is O(J2K′[JL(1/ǫ + log(K′L)) + M ′H log K′]). Here, M ′ is the number of machines; L is the number of homogeneous sub-clusters, J is the number of jobs; K′ is the maximum number of tasks in a job; and H is the number of time slots in the ART table.
In this subsection, we use a simple example to illustrate how BAWMEE achieves energy-efficient workflow mapping without violating precedence constraints. We consider an idle cluster M = C1∪C2 consisting of 4 single-core machines, where C1 = {m1, m2} and C2 = {m3, m4}, and receives a workflow f comprised of homogeneous jobs organized in Fig. 2 with a deadline of 19 time units. The execution time and DEC of a job with a different task partitioning on a different sub-cluster are calculated and listed on the left side of Table 3. BAWMEE first builds a TET for each job on the right side of Table 3. A pipeline {v1, v2, v4, v6, v8} is selected as the initial CP. We assume that ǫ is set to be 0.02. In an approximation solution of pipeline mapping with EST of 0 and LFT of 19, each job has only one task, and v1, v2 and v6 are mapped onto machine m1 in C1 from 0 to 3, from 3 to 6, and from 11 to 14, respectively, and v4 and v8 are mapped onto machine m3 in C2 from 6 to 11 and from 14 to 19, respectively. Then, the second pipeline {v3, v5, v7} is selected as the CP in G − {v1, v2, v4, v6, v8}. In an approximation solution of pipeline mapping with EST of 3 and LFT of 14, v3 intends to have one task and be mapped onto C2 from 3 to 8, and v5 and v7 intend to have one task and be mapped onto C1 from 8 to 11 and from 11 to 14, respectively. Since v3 misses its TLFT of 6, the first sub-pipeline {v3} of {v3, v5, v7} is extracted and the approximation solution of sub-pipeline mapping with EST of 3 and LFT of 6 is that v3 has one task and is mapped onto a machine m2 in C1 from 3 to 6. Subsequently, the third pipeline {v5, v7} is selected as the CP in G − {v1, v2, v3, v4, v6, v8}, and the approximation solution of its mapping with EST of 6 and LFT of 14 is that v5 intends to have one task and be mapped onto C2 from 6 to 9 and v7 intends to have one task and be mapped onto C1 from 9 to 14. Since v7 starts before its TEST of 11, the first sub-pipeline {v5} of {v5, v7} is extracted and the approximation mapping solution of the sub-pipeline with EST of 6 and LFT of 11 is that v5 has one task and is mapped onto a machine m4 in C2 from 6 to 11. Finally, the fourth pipeline {v7} is selected as the CP in G − {v1, v2, v3, v4, v5, v6, v8}, and the approximation solution of its mapping with EST of 11 and LFT of 14 is that v7 has one task and is mapped onto machine m2 in C2 from 11 to 14. Specifically, the mapping result of BAWMEE is shown in Fig. 3(a), and its DEC is 45 units. The optimal mapping is shown in Fig. 3(b), and the minimum DEC is 44 units.
We conduct experiments to illustrate the effect of task
partitioning on job workload and conduct simulations to
evaluate the performance of BAWMEE in comparison with
two existing algorithms adapted from different scenarios: i)
pSciMapper adapted from a workflow mapping algorithm
in [
We consider a computing performance model where the
total workload of a moldable parallel job increases and the
execution time of each task decreases as the number of tasks
increases. For model validation, we conduct an experiment
to illustrate the effect of task partitioning on job workload
for big data applications, which is the foundation of this
research. Towards this goal, we implement a MapReduce
program to find out the most common reason for flight
cancellations based on the airline on-time performance data set
from [
We generate a series of random workflows as follows: (i) randomly select the length L of the critical path of a workflow (no less than 3) and divide the workflow into L layers, in each of which every job has the same length of the longest path from the start job; (ii) randomly select the number of jobs in each layer except the first and last layers, in which there is only one job; (iii) for each job, add an input edge from a randomly selected job in the immediately preceding layer, if absent, and an output edge to a randomly selected job in its downstream layer(s); (iv) randomly pick up two jobs in different layers and add a directed edge from the job in the upstream layer to the job in the downstream layer until we reach the given number of edges. The number of precedence constraints of the workflow is set to 1.5 times of the number of jobs, if possible. The maximum possible number of tasks for each job is randomly selected between 12 and 48. The workload of a job is randomly selected between 0.6 × 1012 and 21.6 × 1012 CPU cycles when running in serial. The workload w(k) of a job with k > 1 tasks is randomly selected between w(k − 1)[1 + 0.2/(k − 1)] and w(k − 1)[1 + 0.6/(k − 1)]. We calculate the sum t1 of the average execution time of the serial jobs on the critical path and the sum t2 of the average execution time of all serial jobs according to the CPU speeds of all types of machines, and randomly select a workflow deadline baseline from the time range [t1, t2]. The percentage of execution time for CPU-bound instructions of a task in each job on each type of machine is randomly selected between 0.1 and 1.0. The memory demand of a task in each job is randomly selected from 0.5GB to 4GB at an interval of 0.5GB.
We evaluate these algorithms in a heterogeneous cluster consisting of machines with four different specifications listed in Table 4, based on 4 types of Intel processors. Each homogeneous sub-cluster has the same number of machines. Each scheduling simulation lasts for 3 days and is repeated 20 times with different workflow instances, whose arrivals follow the Poisson distribution. In the performance evaluation, each data point represents the average of 20 runs with a standard deviation. The parameter ǫ in BAWMEE is set to 0.2. By default, the workflow size is randomly selected between 40 and 60 jobs; the cluster size and the average arrival interval of workflows are set to be 128 machines and 30 minutes, respectively; the deadline factor, which is a coefficient multiplied by the deadline baseline to determine the actual workflow deadline, is set to 0.1.
The dynamic energy consumption reduction (DECR) over the other algorithms in comparison is defined as DECR(Other) = DECOther − DECBAW MEE · 100%, DECOther where DECBAW MEE and DECOther are the average DEC per workflow achieved by BAWMEE and the other algorithm, respectively. The deadline missing rate (DMR) is defined as the ratio of the number of workflows missing their deadlines to the total number of workflows. The unit running time (URT) is measured as the average simulation running time for computing the mapping scheme of each workflow. The simulation runs on a Linux machine equipped with Intel Xeon CPU E5-2620 v3 of 2.4 GHz and a memory of 16 GB.
6.3.1 Problem Size
For performance evaluation, we consider 20 different problem sizes from small to large scales, indexed from 1 to 20 as tabulated in Table 5. Each problem size is defined as a quadruple (|V |, |M |, 1/λ, T ), where 1/λ is the average arrival interval of workflow requests in minutes, and T is the 80 70 )60 % it(cun4500 o d e R30 C E D20 10 BAWMEE over pSciMapper BAWMEE over EEDA time period in unit of days for accepting workflow requests in each simulation. As the workflow size and arrival frequency increase from index 1 to 20, we increase the resources correspondingly to meet tight deadlines with factor 0.1. We plot the DECR, DMR, and URT of pSciMapper, EEDA, and BAWMEE in Figs. 5-7, respectively, which show that BAWMEE saves 58.1% to 67.3% DEC and 22.1% to 40.1% DEC in comparison with pSciMapper and EEDA, respectively, and the DMR of pSciMapper (or EEDA) minus that of BAWMEE is in the range of 42.6% to 93.4% (or 4.1% to 59.7%). Furthermore, the URT of BAWMEE is on the same order of magnitude as those of pSciMapper and EEDA and is less than 7.4 seconds even for problem index 20. 6.3.2 Deadline Constraint
We evaluate the performance of pSciMapper, EEDA, and BAWMEE in terms of DEC, DMR, and URT under different deadline constraints obtained from the deadline baseline multiplied by a factor from 0.05 to 1 with an interval of 0.05. The DEC, DMR, and URT of these algorithms are plotted in Figs. 8-10, respectively. These measurements 320 280 )J240 M ( low200 f rko160 W rep120 EC80 D 40 0 Random show that BAWMEE saves 56.7% to 71.0% DEC and 8.8% to 43.1% DEC as the deadline increases, and reduces DMR from 99.8% and 90.4% to 54.2% with a deadline factor of 0.05 in comparison with pSciMapper and EEDA, respectively. The DMR of BAWMEE is close to zero when the deadline factor is larger than 0.1. Additionally, the URT of BAWMEE is less than 0.6 second and is 89.1% to 1.2 times and 6.6 to 13.2 times of those of pSciMapper and EEDA, respectively. It is worth pointing out that as the deadline increases, the DEC and URT of BAWMEE decrease, because EEPM plays a more significant role than MDPM in BAWMEE. Hence, BAWMEE makes a better tradeoff between DEC and DMR than the other algorithms in comparison at an acceptable cost of running time. 6.3.3 Workflow Size
For scalability test, we run these three algorithms under different average workflow sizes with 5 to 100 jobs per workflow at a step of 5, where the maximum and minimum workflow sizes are 2 jobs more and less than the average workflow size, respectively. We plot the DECR, DMR, and URT of these algorithms in Figs. 11-13, respectively, where we observe that BAWMEE achieves an increasing DECR between 54.8% and 73.2% in comparison with pSciMapper, and between 8.2% and 49.3% in comparison with EEDA. Moreover, BAWMEE only misses less than 3.0% deadlines while pSciMapper and EEDA miss 77.9% to 97.6% and 9.6% to 69.6% deadlines, respectively. For large workflow sizes with 80 to 100 jobs per workflow that impose high resource demands, BAWMEE achieves a DECR between 8.2% and 11.5%, because it significantly reduces DMR (the first objective) from over 54.3% to less than 0.1%, in comparison with EEDA. The DMR of EEDA experiences a slump under the medium workflow sizes because a higher accuracy could be achieved on the execution progress of a smaller workflow than a larger one, while a further increase in the workflow size may lead to a more severe shortage of computing resources. In addition, the URT of BAWMEE is 75.5% to 3.6 times and 1.3 to 10.2 times of those of pSciMapper and EEDA, respectively. 6.3.4 Cluster Size
We run these three algorithms under different cluster sizes of 64 to 256 machines at a step of 16 for scalability test. The DEC, DMR, and URT of these algorithms are plotted in Figs. 14-16, respectively, where we observe that as the number of machines increases, BAWMEE consumes 54.2% to 69.3% and 6.6% to 43.9% less DEC than pSciMapper and EEDA, respectively, hence exhibiting a satisfactory scalability property with respect to the cluster size. Furthermore, DAWMEE only misses 0.1% to 4.0% deadlines while pSciMapper and EEDA miss 77.9% to 98.9% and 7.7% to 78.3% deadlines, respectively. The increase in the cluster size results in a relatively looser deadline and a more flexible workflow mapping, as a result of which, the DMRs of these three algorithms drastically decrease, and BAWMEE has more chances to save energy. Moreover, the URT of BAWMEE is less than 6.4 seconds and is comparable with those of pSciMapper and EEDA. 6.3.5 Workflow Structure
We further investigate these three algorithms with various workflow structures, including a random shape, a chain, a tree, a reverse tree, and a diamond. The DEC, DMR, and URT are plotted in Figs. 17-19, respectively, which show that BAWMEE reduces DEC by 63.6%, 56.6%, 86.3%, 86.5% and 86.2% as well as by 27.6%, 14.7%, 72.1%, 72.5% and 72.2% in comparison with pSciMapper and EEDA in random, chain, tree, reverse tree and diamond structured workflows, respectively. Further, BAWMEE saves less energy in chain-structured workflows than others, because the deadline baseline is set to be the tightest for this structure based on our deadline generation method. BAWMEE only misses 0.2%, 0%, 1.6%, 0% and 0% deadlines, while pSciMapper and EEDA miss 89.7%, 100%, 58.0%, 71.9% and 61.6% deadlines, and 12.3%, 32.8%, 3.2%, 4.6% and 3.4% deadlines in random, chain, tree, reverse tree and diamond structured workflows, respectively. Besides, the URT of BAWMEE is less than 0.6 second, and is 1.0 times, 4.5 times, 1.1%, 0.4% and 0.4%, as well as 9.4 times, 12.7 times, 16.5%, 9.1% and 6.4% of those of pSciMapper and EEDA in random, chain, tree, reverse tree and diamond structured workflows, respectively.
We investigated the property of moldable jobs and formulated a workflow mapping problem to minimize dynamic energy consumption under deadline and resource constraints. We designed an FPTAS for a special case with a pipelinestructured workflow on a homogeneous cluster, which was proved to be NP-complete, and a heuristic for a generalized problem with an arbitrary workflow on a heterogeneous cluster. The performance superiority of the proposed heuristic in terms of dynamic energy saving and deadline missing rate was illustrated by extensive simulation results in Hadoop/YARN in comparison with existing algorithms.
Our work reveals that the energy-efficient and
deadlineaware mapping algorithms tailored to big data workflows
could lead to significant energy savings and a higher level of
Quality of Service. It is of our future interest to incorporate
the proposed mapping algorithms into the existing workflow
engines in the Hadoop ecosystem including Oozie [
This research is sponsored by National Science Foundation under Grant No. CNS-1560698 with New Jersey Institute of Technology. 9