Online makespan minimization for MapReduce scheduling on multiple parallel machines

• Autorzy: Zheng Quanchang , Zhao Yueyang , Wang Jiahe

Identyfikatory

DOI

10.1515/dema-2024-0040

• Języki publikacji: EN

Abstrakty

EN

In this work, we investigate the online MapReduce processing problem on m uniform parallel machines, aiming at minimizing the makespan. Each job consists of two sets of tasks, namely, the map tasks and the reduce tasks. A job’s map tasks can be arbitrarily split and processed on different machines simultaneously, while its reduce tasks can only be processed after all its map tasks have been completed. We assume that the reduce tasks are preemptive, but cannot be processed on different machines in parallel. We provide a new lower bound for this problem and present an online algorithm with a competitive ratio of 2-1/m (m is the number of machines) when the speeds of the machines are 1.

Słowa kluczowe

EN

MapReduce scheduling; online algorithm; competitive ratio; parallel machines; lower bound

• Wydawca: De Gruyter
• Czasopismo: Demonstratio Mathematica
• Rocznik: 2024
• Tom: Vol. 57, nr 1
• Strony: art. no. 20240040
• Opis fizyczny: Bibliogr. 17 poz., rys.

Twórcy

autor

Zheng Quanchang

• Institute of Operational Research, Qufu Normal University, Rizhao, Shandong, 276800, P. R. China

autor

Zhao Yueyang

• School of Management Science, Gachon University, Gyeonggi-do, 826802, South Korea

autor

Wang Jiahe

• Institute of Operational Research, Qufu Normal University, Rizhao, Shandong, 276800, P. R. China

Bibliografia

• [1] J. Dean and S. Ghemawat, MapReduce: simplified data processing on large clusters, Commun. ACM 51 (2008), 107–113, DOI: https://doi.org/10.1145/1327452.1327492.
• [2] M. Isard, V. Prabhakaran, J. Currey, U. Wieder, K. Talwar and A. Goldberg, Quincy: Fair scheduling for distributed computing clusters, Proceedings of ACM SIGOPS 22nd Symposium on Operating Systems Principles, (Big Sky Montana USA), 209, October 11–14, pp. 261–276, DOI: https://doi.org/10.1145/1629575.1629601.
• [3] M. Zaharia, D. Borthakur, J. Sarma, K. Elmeleegy, S. Shenker and I. Stoica, Delay scheduling: A simple technique for achieving locality and fairness in cluster scheduling, Proceedings of Fifth EuroSys Conference 2010, (Paris France), 2010, April 13–16, pp. 265–278, DOI: https://doi.org/10.1145/1755913.1755940.
• [4] L. Kolb, A. Thor, and E. Rahm, Load balancing for mapreduce based entity resolution, Proceedings of 2012 IEEE 28th International Conference on Data Engineering, 2012, April 1–5, pp. 618–629, DOI: https://doi.org/10.1109/ICDE.2012.22.
• [5] A. Bechini, F. Marcelloni, and A. Segatori, A MapReduce solution for associative classification of big data, Inf. Sci. 332 (2016), 33–55, DOI: https://doi.org/10.1016/j.ins.2015.10.041.
• [6] B. Moseley, A. Dasgupta, R. Kumar, and T. Sarlós, On scheduling in Map-Reduce and flow-shops, Proceedings of 23rd ACM Symposium on Parallelism in Algorithms and Architectures, (San Jose California USA), 2011, June 4–6, pp. 289–298, DOI: https://doi.org/10.1145/1989493.1989540.
• [7] Y. Zheng, N. Shroff, and P. Sinha, A new analytical technique for designing provably efficient MapReduce schedulers, Proceeding of 2013 Proceedings IEEE INFOCOM, 2013, April 14–19, pp. 1600–1608, DOI: https://doi.org/10.1109/INFCOM.2013.6566956.
• [8] Y. Zhu, Y. Jiang, W. Wu, L. Ding, A. Teredesai, D. Li, et al., Minimizing makespan and total completion time in MapReduce-like systems, Proceeding of IEEE INFOCOM 2014 - IEEE Conference on Computer Communications, 2014, pp. 2166–2174, DOI: https://doi.org/10.1109/INFOCOM.2014.6848159.
• [9] T. Luo, Y. Zhu, W. Wu, Y. Xu, and D. Du, Online makespan minimization in MapReduce-like systems with complex reduce tasks, Optim. Lett. 2015 (2015), 271–277, DOI: https://doi.org/10.1007/s11590-015-0902-7.
• [10] H. Chang, M. Kodialam, R. Kompella, T. Lakshman, M. Lee, and S. Mukherjee, Scheduling in MapReduce-like systems for fast completion time, Proceeding of IEEE INFOCOM, 2011, pp. 3074–3082, DOI: https://doi.org/10.1109/infcom.2011.5935152.
• [11] Y. Jiang, W. Zhou, and P. Zhou, An optimal preemptive algorithm for online MapReduce scheduling on two parallel machines, Asia-Pac. J. Oper. Res. 35 (2018), 185003, DOI: https://doi.org/10.1142/S0217595918500136.
• [12] J. Huang, F. Zheng, Y. Xu, and M. Liu, Online MapReduce processing on two identical parallel machines, J. Comb. Optim. 35 (2018), 216–223, DOI: https://doi.org/10.1007/s10878-017-0167-4.
• [13] Y. Jiang, P. Zhou, T. Cheng, and M. Ji, Optimal online algorithms for MapReduce scheduling on two uniform machines, Optim. Lett. 13 (2019), 1663–1676, DOI: https://doi.org/10.1007/s11590-018-01384-8.
• [14] C. Chen, Y. Xu, Y. Zhu, and C. Sun, Online MapReduce scheduling problem of minimizing the makespan, J. Comb. Optim. 33 (2017), 590–608, DOI: https://doi.org/10.1007/s10878-015-9982-7.
• [15] R. Jeyaraj, V.S. Ananthanarayana, and A. Paul, Improving MapReduce scheduler for heterogeneous workloads in a heterogeneous environment, Concurr. Comput. Pract. Exp. 32 (2020), 1–10, DOI: https://doi.org/10.1002/cpe.5558.
• [16] X. Li, F. Chen, R. Ruiz, and J. Zhu, MapReduce task scheduling in heterogeneous geo-distributed data centers, IEEE Trans. Serv. Comput. 15 (2022), 3317–3329, DOI: https://doi.org/10.1109/TSC.2021.3092563.
• [17] X. Wang, C. Wang, M. Bai, Q. Ma, and G. Li, HTD: heterogeneous throughput-driven task scheduling algorithm in MapReduce, Distrib. Parallel. Dat. 40 (2022), 135–163, DOI: https://doi.org/10.1007/s10619-021-07375-6.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa nr POPUL/SP/0154/2024/02 w ramach programu "Społeczna odpowiedzialność nauki II" - moduł: Popularyzacja nauki (2026).