Research On Multi-resource Allocation And Scheduling In Data-intensive Computing Environment

Data-intensive computing has promoted the efficient processing of huge data and the rapid data-intensive application development.Increasing number of data-intensive applications raises a higher demand for multi-resource allocation and scheduling,which lies in the multi-resource fair allocation for different data-intensive applications,and the multi-resource scheduling to optimize both energy consumption and performance and the resource provider profit.Base on Mapreduce,the dissertation studies multi-resource fair allocation and multi-resource scheduling optimization in data-intensive computing environment.The main contributions of this dissertation are listed as follows:(1)Aiming at the multi-resource fair allocation based on divisible tasks in single-machine computing environment,this dissertation proposes three fair allocation strategies for different data-intensive applications.A static multi-resource fair allocation strategy brought by different shared resource quantities and the bounded number of tasks is proposed,which establishes a general p norm lexicographically max-min fair allocation model and designs a heuristic algorithm based on binary search to find a near-optimal solution in polynomial time.Second,a dynamic multi-resource fair allocation strategy brought by different shared resource quantities is proposed,which establishes a dynamic and fair allocation model for the dominant resource based on the shared resource quantity and designs a dynamic allocation algorithm using binary search to find a near-optimal solution in polynomial time.Third,a dynamic multi-resource fair allocation strategy brought by the bounded number of tasks is proposed,which establishes a dynamic and fair allocation model for the dominant resource based on the number of tasks and designs a dynamic allocation algorithm using binary search which finds a near-optimal solution in polynomial time.The above three strategies are proved to satisfy fairness properties.The experimental results also show that the three strategies can effectively guarantee fairness and allocation efficiency.(2)Aiming at the multi-resource fair allocation based on indivisible tasks in multi-machine computing environment,this dissertation proposes a multi-resource fair allocation strategy based on discrete interior search algorithm.The strategy establishes a global dominant resource fair allocation model and adopts a discrete interior search algorithm to obtain a near-optimal integer allocation.And a repair operator is designed to find the feasible solution.The experimental results show that the strategy is better than other DRFHs in terms of global dominant share,resource utilization and algorithm efficiency.(3)Aiming at the energy consumption and makespan optimization of the Mapreduce resource scheduling,this dissertation proposes a resource scheduling model based on task types and slot types and designs a two-stage heuristic algorithm and a NSGA-II algorithm.The two-stage heuristic algorithm is to find a high-quality feasible solution.Then,with the feasible solution taken as part of the initial population,the NSGA-II is adopted to get a set of near-Pareto optimal solutions.The experimental results show that the proposed method can quickly obtain a set of near-Pareto optimal schedulings to tradeoff energy consumption and makespan.(4)Aiming at the profit optimization of Mapreduce job processing,the dissertation proposes a maximum profit per unit time model for a single job,and presents a bipartite graph b-matching rounding algorithm,which transforms the nonlinear integer programming model into a linear programming model,and the linear programming optimal solution is used to construct bipartite graphs.By b-matching rounding method,a near-optimal integer solution is obtained.In addition,a profit per unit time function for a set of job is proposed,and the offline and online scheduling algorithms are designed to obtain resource scheduling and job scheduling to maximize the profit per unit time.The experimental results show that the proposed algorithms outperform other algorithms in profit optimization.