ارائه یک الگوریتم زمانبندی جدید برای کاهش زمان محاسبات در محیط هادوپ

نوع مقاله : مقاله پژوهشی

نویسندگان

1 مربی گروه کامپیوتر، دانشگاه علمی‌– کاربردی، دهدشت، ایران

2 دانشجوی کارشناسی‌ارشد، دانشگاه افسری و تربیت پاسداری امام حسین(ع)

چکیده

امروزه پروژه متن‌باز هادوپ به‌همراه چهارچوب نگاشت-کاهش در بین مؤسسات، سازمان‌ها و محققین محبوبیت زیادی دارد که برای پردازش حجم انبوهی از داده‌ها به‌صورت موازی بر روی خوشه‌ای از کامپیوتر‌ها بسیار مناسب است. نگاشت-کاهش برای حل مشکلات محاسبات داده‌های حجیم معرفی شده است که از قاعده تقسیم-غلبه پیروی می‌کند. مانند هر جای دیگر، مبحث زمان و زمان‌بندی در نگاشت-کاهش از اهمیت بسیار بالایی برخوردار است. به‌همین دلیل در دهه اخیر الگوریتم‌های زمانبندی متعددی در این زمینه تدارک یافته است. ایده اصلی این الگوریتم‌ها افزایش نرخ محلی‌‌سازی داده، هم­زمان‌سازی، کاهش زمان پاسخ و زمان اتمام وظایف می‌باشد. اکثر این الگوریتم‌ها تک هدفه می‌باشند و فقط یکی از موارد ذکر شده را مورد هدف قرار می‌دهند. الگوریتم­های چند هدفه موجود فقط بر روی یکی از فازهای اول یا دوم نگاشت-کاهش تمرکز دارند. در این مقاله، یک الگوریتم زمان­بندی ترکیبی مبتنی بر اولویت‌بندی پویا کار‌ها و محلی‌‌سازی داده در محیط نگاشت‌-کاهش به نام "HSMRPL" ارائه می‌‌شود که هدف اصلی آن افزایش نرخ محلی‌سازی داده و کاهش زمان محاسبات می‌باشد. در این الگوریتم از دو روش اولویت‌بندی پویا و شناسه محلی‌‌سازی استفاده می‌شود. برای ارزیابی الگوریتم پیشنهادی، آن‌ را با الگوریتم‌های پیش‌فرض هادوپ و به کمک محک‌های استاندارد مقایسه کردیم. نتایج حاصله نشان می‌دهد که الگوریتم پیشنهادی ما نرخ محلی‌سازی را نسبت به الگوریتم FIFO، 5/18 درصد و نسبت به الگوریتم Fair، 4/10 درصد افزایش داده است. همچنین، الگوریتم پیشنهادی ما نسبت به الگوریتم FIFO، 8/3 درصد و نسبت به Fair، 4/13 درصد سریعتر است.

کلیدواژه‌ها


[1]     J. Dean and S. Ghemawat, “MapReduce: Simplified Data Processing On Large Clusters,” Communications of the ACM, vol. 51(1), pp. 107-113, 2008.##
[2]     M. Zaharia, A. Konwinski, A. D. Joseph, R. H. Katz, and I. Stoica, “Improving MapReduce Performance in Heterogeneous Environments,” In OSDI, vol. 8, no. 4, p. 7, 2008.##
[3]     T. White, “Hadoop: The definitive guide,” O'Reilly Media, Inc., 2012.##
[4]     S. Perera, “Hadoop MapReduce Cookbook,” Packt Publishing Ltd, 2013.##
[5]     S. R. Pakize, “A Comprehensive View of Hadoop Map Reduce Scheduling Algorithms,” International Journal of Computer Networks and Communications Security, ISSN, pp. 2308-9830, 2014.##
[6]     V. Prajapati, “Big Data Analytics with R and Hadoop,” Packt Publishing Ltd, 2015.##
[7]     I. Hashem, T. Abaker, et al., “MapReduce Scheduling Algorithms: a review,” The Journal of Supercomputing, pp. 1-31, 2018.##
[8]     K. Hadjar and A. Jedidi, “A New Approach for Scheduling Tasks and/or Jobs in Big Data Cluster,” 4th MEC International Conference on Big Data and Smart City (ICBDSC), IEEE, 2019.##
[9]     M. Zaharia, D. Borthakur, J. Sen Sarma, K.Elmeleegy, S. Shenker, and I. Stoica, “Delay Scheduling: A Simple Technique for Achieving Locality and Fairness in Cluster Scheduling,” In Proceedings of the 5th European conference on Computer systems, pp. 265-278, 2010.##
[10]  Q. Chen, D. Zhang, M. Guo, Q. Deng, and S. Guo, “Samr: A Self-adaptive Mapreduce Scheduling Algorithm in Heterogeneous Environment,” In Computer and Information Technology (CIT), IEEE 10th International Conference on, pp. 2736-2743, 2010.##
[11]  L. Lei, T. Wo, and C. Hu, “CREST: Towards Fast Speculation of Straggler Tasks in MapReduce,” In e-Business Engineering (ICEBE), IEEE 8th International Conference on, pp. 311-316, 2011.##
[12]  C. He, Y. Lu, and D. Swanson, “Matchmaking: A new Mapreduce Scheduling Technique,” In Cloud Computing Technology and Science (CloudCom), IEEE Third International Conference on, pp. 40-47, 2011.##
[13]  P. Nguyen, T. Simon, M. Halem, D. Chapman, and Q. Le, “A Hybrid Scheduling Algorithm for data Intensive Workloads in a Mapreduce Environment,” In Proceedings of the IEEE/ACM Fifth International Conference on Utility and Cloud Computing, pp. 161-167, 2012.##
[14]  S. Ibrahim, H. Jin, L. Lu, B. He, G. Antoniu, and S. Wu, “Maestro: Replica-aware Map Scheduling for Mapreduce,” In Cluster, Cloud and Grid Computing (CCGrid), 12th IEEE/ACM International Symposium on, pp. 435-442, 2012.##
[15]  F. Ahmad, S. Lee, M. Thottethodi, and T. N. Vijaykumar, “MapReduce with Communication Overlap (MaRCO),” Journal of Parallel and Distributed Computing, vol. 73(5), pp.           608-620, 2013.##
[16]  A.Rasooli and D. G. Down, “COSHH: A Classification and Optimization Based Scheduler for Heterogeneous Hadoop systems,” Future Generation Computer Systems, vol. 36, pp.       1-15, 2014.##