三台同类机MapReduce排序问题的最优算法
|
摘要
研究MapReduce环境下的可中断同类平行机排序问题。在MapReduce环境中,每个工件含有两种类型的任务集,即Map任务集和Reduce任务集。在加工完工件的Map任务集后才能开始加工Reduce任务集中的任务。考虑Map任务为可分的情况,即Map任务可以任意分割为不同的小任务并能在不同机器上同时进行并行加工,而对于Reduce任务则考虑允许中断的情形,目标设为极小化最大完工时间。针对三台同类机的离线排序问题,通过分解所有实例的类型,给出了最优解算法。
Interruptible uniform parallel machine scheduling under MapReduce environment is studied in this paper. Under MapReduce environment, each workpiece contains two types of task sets: namely Map task set and Reduce task set. The tasks in Reduce task set can only be processed after finishing all tasks in Map tasks. The Map tasks are separable, i.e., they can be arbitrarily split into different small tasks and processed on different machines in parallel. Interruption is considered for Reduce tasks. Our objective is to minimize the maximum makespan. For the offline scheduling problem of three uniform machines, an optimum solution algorithm is provided by the analysis of the types of all instances.
Interruptible uniform parallel machine scheduling under MapReduce environment is studied in this paper. Under MapReduce environment, each workpiece contains two types of task sets: namely Map task set and Reduce task set. The tasks in Reduce task set can only be processed after finishing all tasks in Map tasks. The Map tasks are separable, i.e., they can be arbitrarily split into different small tasks and processed on different machines in parallel. Interruption is considered for Reduce tasks. Our objective is to minimize the maximum makespan. For the offline scheduling problem of three uniform machines, an optimum solution algorithm is provided by the analysis of the types of all instances.
引文
[1] Dean J,Ghemawant S.MapReduce:Simplified data processing on large clusters[J].Communications of the ACM,2008,51(1):107-113.
[2] Isard M,Prabhakaran V,Currey J,et al.Quincy:Fair scheduling for distributed computing clusters[C]//Proceedings of the ACM SIGOPS 22nd Symposium on Operating Systems Principles,New York:IEEE,2009:261-276.
[3] Gufler B,Augsten N,Reiser A,et al.Load balancing in mapreduce based on scalable cardinality estimates[C]//In Data Engineering (ICDE) 2012 IEEE 28th International Conference on,Italy:IEEE,2012:522-533.
[4] Bechini A,Marcelloni F,Segatori A.A MapReduce solution for associative classification of big data[J].Information Sciences,2015,332:33-55.
[5] Zhu Y,Jiang Y,Wu W,et al.Minimizing makespan and total completion time in MapReduce-like systems[C]// In INFOCOM’14.IEEE,2014:2166-2174.
[6] Jiang Y,Zhu Y,Wu W,et al.Makespan minimization for MapReduce systems with different servers[J].Future Generation Computer Systems,2017,67:13-21.
[7] 周维.若干MapReduce排序问题的算法研究[D].杭州:浙江理工大学,2017:5-11.
[8] Jiang Y,Zhou W,Zhou P.An optimal preemptive algorithm for online MapReduce scheduling on two parallelmachines[J].Asia-Pacific Journal of Operational Research,2018,35(3):1850013.
[9] Luo T,Zhu Y,Wu W,et al.Online makespan minimization in MapReduce like systems with complex reduce tasks[J].Optimization Letters,2017,11(2):271-277.
[10] Chen C,Xu Y,Zhu Y,et al.Online MapReduce scheduling problem of minimizing the makespan[J].Journal of Combinatorial Optimization,2017,33(2):590-608.
[11] Le Y,Liu J,Ergun F,et al.Online load balancing for MapReduce with skewed data input[C]//IEEE INFOCOM 2014 - IEEE Conference on Computer Communications.IEEE,2014:2004-2012.
[12] Gonzalez T,Sahni S.Preemptive scheduling of uniform processor systems[J].Journal of the Acm,1978,25:92-101.
[2] Isard M,Prabhakaran V,Currey J,et al.Quincy:Fair scheduling for distributed computing clusters[C]//Proceedings of the ACM SIGOPS 22nd Symposium on Operating Systems Principles,New York:IEEE,2009:261-276.
[3] Gufler B,Augsten N,Reiser A,et al.Load balancing in mapreduce based on scalable cardinality estimates[C]//In Data Engineering (ICDE) 2012 IEEE 28th International Conference on,Italy:IEEE,2012:522-533.
[4] Bechini A,Marcelloni F,Segatori A.A MapReduce solution for associative classification of big data[J].Information Sciences,2015,332:33-55.
[5] Zhu Y,Jiang Y,Wu W,et al.Minimizing makespan and total completion time in MapReduce-like systems[C]// In INFOCOM’14.IEEE,2014:2166-2174.
[6] Jiang Y,Zhu Y,Wu W,et al.Makespan minimization for MapReduce systems with different servers[J].Future Generation Computer Systems,2017,67:13-21.
[7] 周维.若干MapReduce排序问题的算法研究[D].杭州:浙江理工大学,2017:5-11.
[8] Jiang Y,Zhou W,Zhou P.An optimal preemptive algorithm for online MapReduce scheduling on two parallelmachines[J].Asia-Pacific Journal of Operational Research,2018,35(3):1850013.
[9] Luo T,Zhu Y,Wu W,et al.Online makespan minimization in MapReduce like systems with complex reduce tasks[J].Optimization Letters,2017,11(2):271-277.
[10] Chen C,Xu Y,Zhu Y,et al.Online MapReduce scheduling problem of minimizing the makespan[J].Journal of Combinatorial Optimization,2017,33(2):590-608.
[11] Le Y,Liu J,Ergun F,et al.Online load balancing for MapReduce with skewed data input[C]//IEEE INFOCOM 2014 - IEEE Conference on Computer Communications.IEEE,2014:2004-2012.
[12] Gonzalez T,Sahni S.Preemptive scheduling of uniform processor systems[J].Journal of the Acm,1978,25:92-101.