Fast Pruning Algorithm and Task Scheduling under Map/Reduce

doi:10.23940/ijpe.20.10.p14.16271636

Abstract

Abstract: In the cloud environment, the resource utilization and overall efficiency of traditional task allocation and scheduling algorithms are very low. In order to improve the overall efficiency of Map/Reduce processing task allocation and improve the resource utilization efficiency of nodes, a pruning algorithm based on task processing time is proposed. In the pruning algorithm, the processing time of each task in each node is used for quantitative modeling, the task and processing time measurement matrix is established, and the rank pruning method is used to reduce the size of the assigned tasks. Only by assigning (N-1) tasks can the allocation problem of N nodes processing N tasks be solved, and the optimal solution of the task can be obtained. This article uses MATLAB to simulate the cloud environment and compares the pruning algorithm with traditional algorithms (including FIFO scheduling and capacity scheduling algorithms). Simulation results show that the pruning algorithm can significantly improve the overall efficiency of task scheduling under a large amount of data testing, and make full use of the computing power of nodes to improve the efficiency of Map/Reduce scheduling.

Key words: pruning optimization, task scheduling, cloud environment, Hadoop, Map/Reduce

Shujun Pei, Yu Zhang, and Chao Liang. Fast Pruning Algorithm and Task Scheduling under Map/Reduce [J]. Int J Performability Eng, 2020, 16(10): 1627-1636.

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

References

1. H. L. Shi, “Research of Job Scheduling on Cloud Computing,” Nanjing University of Science Technology, 2015
2. D. Y. Zhang, T. M. Jiang,S. Wu, “Brief Talk on Cloud Computing Technology,” 2020
3. Z. J. Tang, “Research on the Design of Cloud Computing Platform in Intelligent Campus,” Journal of Physics: Conference Series, Vol.1237, No. 2, 2019
4. M. Kumar, S. C. Sharma, A. Goel,S. P. Singh, “A Comprehensive Survey for Scheduling Techniques in Cloud Computing,”Journal of Network and Computer Applications, Vol. 143, pp. 1-33, 2019
5. L. Xu, et al., “Research on the Task Assignment Problem with Maximum Benefits in Volunteer Computing Platforms,” 2020
6. J. Niu and C. Lin, “Research on Power Distribution Control Method of Hybrid Electric Vehicle,”Automotive Practical Technology, No. 3, pp. 109-112, 2016
7. D. X.Xin and F. Liu, “Research of Hadoop Performance Tuning Technology,”Computer Knowledge and Technology, No. 22, pp. 5484-5486, 2011
8. Y. Z. He, “Performance Analysis and Optimization of Map/Reduce,” Huazhong University of Science and Technology, 2012
9. J. J. Li, Y. J. Liu, J. Pan, P. Zhang, W. Chen,L. Z. Wang, “Map-Balance-Reduce: An Improved Parallel Programming Model for Load Balancing of MapReduce,” Future Generation Computer Systems, Vol. 105, No. C, 2020
10. Y. Lin, Y. Li, X. Yin, et al., “Multisensor Fault Diagnosis Modeling based on the Evidence Theory,” IEEE Transactions on Reliability, Vol. 67, No. 2, pp. 513-521, 2018
11. Y. Lin, C. Wang, J. X. Wang,Z. Dou, “A Novel Dynamic Spectrum Access Framework based on Reinforcement Learning for Cognitive Radio Sensor Networks,” Sensors, Vol. 16, No. 10, pp. 1675, 2016
12. J. Zhu, “Research on Data Mining of Electric Power System based on Hadoop Cloud Computing Platform,” International Journal of Computers and Applications, Vol. 41, No. 4, 2019
13. Y. Lin, X. Zhu, Z. Zheng, et al., “The Individual Identification Method of Wireless Device based on Dimensionality Reduction and Machine Learning,”Journal of Supercomputing, No. 5, pp. 1-18, 2017
14. Y. Tu, Y. Lin, J. Wang, et al., “Semi-Supervised Learning with Generative Adversarial Networks on Digital Signal Modulation Classification,” CMC-Computers Materials and Continua, Vol. 55, No. 2, pp. 243-254, 2018
15. C. J. Tao, “Reduce Task Scheduling base on Task Time,” Computer Engineering and Design, Vol. 37, No. 3, 2016
16. H. Yang, A. Darden, R. Hsiao,D. Parker, “Map-Reduce-Merge: Simplified Relational Data Processing on Large Clusters,” in Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data, New York, 2007
17. Y. H. Ma, “A Faster Pruning Optimization Algorithm for Task Assignment,” Journal of Northwestern Polytechnic University, Vol. 31, No. 1, 2013
18. K. Kc and K. Anyanwu, “Scheduling Hadoop Jobs to Meet Deadlines,” inProceedings of IEEE 2^nd International Conference on Cloud Computing Technology and Science (C1oudCom), pp. 388-392, 2011
19. Y. H. Huang, “Understanding Big Data: Big Data Processing and Programming,” China Machine Press, Beijing, 2014
20. X. R. Zhou, Z. S. Teng,Z. Yi, “Fast Pruning Algorithm for Designing Sparse Least Squares Support Vector Machine,” Electric Machines and Control, Vol. 13, No. 4, 2009
21. J. P. Zhang, “Optimization and Research of Scheduling in Cloud Computing based on Map/Reduce Cluster Model,” Nanjing University of Posts and Telecommunications, 2014
22. J. Dean and S. Ghemawat, “Map/Reduce: Simplified Data Processing on Large Clusters,” pp. 107-113, ACM, New York, USA, 2013

[1]	Sonia Sharma and Rajendra Kumar Bharti. Intelligent Job Allocation and Adaptive Migration in Cloud Environments using a Dynamic Dual-Threshold Strategy [J]. Int J Performability Eng, 2025, 21(3): 168-177.
[2]	Ammar Zakzouk, Bassim Oumran, and Hasan Hasan. ALLI: A High-Performance Approach to Data Deduplication in Hadoop using Enhanced Hashing and Two-Level Indexing Techniques [J]. Int J Performability Eng, 2024, 20(12): 741-752.
[3]	Priyanshu Verma, Ishan Sharma, Sonia Deshmukh, and Rohit Vashisht. Customer Churn Analysis using Spark and Hadoop [J]. Int J Performability Eng, 2023, 19(10): 663-675.
[4]	Xuan Chen, Zhengjiang Song, Hongfeng Zheng, and Zhiping Wan. Task Scheduling based on Fruit Fly Optimization Algorithm in Mobile Cloud Computing [J]. Int J Performability Eng, 2020, 16(4): 618-628.
[5]	Yan Li and Yao Yao. Scheduling Algorithm for a Task under Cloud Computing [J]. Int J Performability Eng, 2019, 15(8): 2081-2090.
[6]	Haodong Zhu, Wenqi Li, and Hongchan Li. Feature Dimension Reduction Optimization Algorithm for Massive Micro-Blog Data based on Hadoop [J]. Int J Performability Eng, 2019, 15(6): 1518-1527.
[7]	Ge Jiao, Lang Li, and Yi Zou. Improved Security for Android System based on Multi-Chaotic Maps using a Novel Image Encryption Algorithm [J]. Int J Performability Eng, 2019, 15(6): 1692-1701.