Research On Energy Consumption And Makespan Of Scheduling Workflow In Heterogeneous Distributed Computing System

The heterogeneous distributed computing system(HDCS),which is characterized by its powerful computing power,convenient deployment,and resource management flexibility and so on,plays an important role in industry and academia.Meanwhile,large-scale businesses and scientific applications,which are usually composed of big-data,multitasking,time-variant,and fluctuating workloads,have become the mainstream of current technologies.As a result,HDCS has a tightly coupled relationship with the large-scale workflow/application.Consequently,the huge system and application must have a huge demand for energy consumption.How to reduce the overall energy consumption of the system while satisfying the quality of service(QoS)is a problem to be solved urgently.This paper focuses on the scheduling problem of workflow in dynamic voltage-frequency scaling(DVFS)enabled HDCS.In particularly,the workflow could be represented by directed acyclic graph(DAG).For different QoS constraints,we addressed several problems which are focused on time and energy optimization.Our main contributions are listed as below:(1)We propose an energy optimization heuristic for deadline-constrained workflows in HDCS,named Backward Frog-leaping global Energy Conscious Scheduling(BFECS).Most of existing energy optimization heuristics with deadline constraint for workflows in DVFS-enabled HDCS usually trap in local optima.In this paper,we propose a new energy optimization heuristic called backward frog-leaping global energy conscious scheduling:BFECS.This algorithm makes full use of surplus time between the lowerbound of the workflow and the constrained deadline.Specifically,it starts from the constrained deadline,and leapfrogs towards the lowerbound of the workflow with different leap interval.During the whole process of leapfrogging,the leap intervals are continually changed according to the locally optimal value until the endpoint of leapfrogging is reached;the scheduling sequence with least energy consumption is also saved at the same time.Furthermore,more energy consumption can be reduced by leveraging slack time reclamation technique,and the idle time slots caused by precedence constraints can be assimilated by the tasks through running at a lower and suitable voltage/frequency using DVFS technique,without violating the precedence constraints of the workflow and breaking the deadline.The experimental results show that the proposed algorithm can decrease energy consumption significantly.(2)We propose two energy optimization heuristics for budget-constrained workflow in HDCS,which are Minimum-Cost-Up-to-Budget(MCUB)and Maximum-Cost-Down-to-Budget(MCDB),resepectively.With the rapid development of commercialized computation,the HDCS has evolved into a new method of service provisioning based on utility computing models,in which the users consume services and resources based on their quality of service requirements.In certain models using the "pay-as-you-go" concept,the users are charged for accessed services based on their usage.Given that the user usually could pay limited money to rent service.In addition,the commercialized HCS provider also assumes the responsibility to reduce the energy consumption to protect the environment.This paper considers a basic model known as DAG,which is designed for workflow applications,and also investigates heuristics that allows the scheduling of various tasks of a workflow into the DVFS-enabled HDCS,in a manner that satisfies cost budget while also allowing effective optimization for overall energy consumption.Other significant factors concerning the financial aspect are also considered,where the application of two different approaches is used,namely,MCUB and MCDB.These approaches,along with their variants,are implemented and evaluated using four types of basic DAGs.From the experimental results,we conclude that MCDB outperforms MCUB in energy optimization and makespan criterion while meeting budget constraints defined by users.(3)For multiple workflows computing in HDCS,one of challenging issues is how to make a reasonable tradeoff between the schedule length and energy consumption.In this thesis,based on four intial scheduling strategies for multiple DAG workflows,we propose five algorithms,namely,Sequential,RoundRobin,GapSearch,Interleaving and MergeOne,to schedule multiple workflows onto HDCS and then propose an algorithm named multiple workflows slack time teclaiming(MWSTR)to optimize the all energy consumption of the whole schedule list.We also evaluate the algorithms in terms of randomly generated DAGs,real application DAGs and their hybrids under DVFS-enabled HDCS.From the experimental results,we draw the conclusion that the combination of Interleaving and MWSTR can lead to a better average tradeoff when scheduling multiple workflows in HDCS.