Research On Energy-saving Workflow Scheduling Based On Hypergraph

As an emerging thing in the early 21st century,cloud computing has entered a mature stage of development.Relying on virtualization technology,it integrates and manages all kinds of resources effectively,so that users are provided with efficient computing services and applications.In recent years,the workflows have become increasingly complex that are generated by academic researches,such as image processing earthquake prediction,genome sequencing and so on.And more and more workflows are submitted to the cloud for processing.In order to meet the computing requirements of different users in different scenarios,cloud service providers at home and abroad have been upgrading and expanding cloud data centers.However,the average resource utilization of hosts is poor in cloud data centers,which causes high energy consumption to be the key problem that cloud service providers need to solve as quickly as possible.Reasonable energy-saving workflow scheduling strategy is an effective way to solve the above problem,and it's of practical significance for cloud resource scheduling.This paper systematically studies energy-saving technologies,the workflow models and workflow scheduling algorithms,and then analyzes the problems and difficulties in the existing work.Considering the current development of cloud computing,we study workflow modeling and partitioning based on hypergraph,and research on multi-objective oriented workflow scheduling,so as to reduce the energy consumption of cloud data centers,and meanwhile to satisfy users with the quality of service.The main work can be summarized as the following two points:(1)Research on workflow modeling and partitioning based on hypergraph.An accurate descriptive model of workflow is the key precondition for a good scheduling algorithm.This paper establishes a new model for workflow based on hypergraph,which focuses on data transmission in the execution process of workflow and complex data dependencies among tasks in a workflow.Tasks connect with each other using a hyperedge if they rely on the same data file,which overcomes the disadvantage that directed acyclic graph can only express one-to-one relationship.On this basis,a Directed Hypergraph based Energy-Saving Workflow Partitioning Strategy(HPWS)is proposed to divide a workflow into the least number of partitions and assign them to hosts,through hypergraph coarsening,hypergraph partitioning and partition scheduling.The experimental results show that HPWS enables the minimum hosts to execute the workflow,and then reduce the energy consumption of cloud data centers.(2)Research on multi-objective oriented workflow scheduling.In order to further reduce the makespan of workflow and reduce the energy consumption of data center at the same time,this paper studies a time-saving and energy-saving workflow scheduling strategy after the workflow has been allocated to the appropriate servers using HPWS.Considering the influence of dependencies between tasks on scheduling results,the priority of tasks is proposed by both the earliest completion time and the impact factor.Furthermore,the time loss of scheduling virtual machines is compared among tasks with the same priority,and the Least Time Loss based Dependent Task Scheduling Algorithm(LLTS)is proposed to schedule tasks to virtual machines running in the host chosen by HPWS.The experimental results show that LLTS can further shorten the workflow makespan,especially for the workflow with more parallel tasks.