Abstract:
امروزه پروژه متنباز هادوپ بههمراه چهارچوب نگاشت-کاهش در بین موسسات، سازمانها و محققین محبوبیت زیادی دارد که برای پردازش حجم انبوهی از دادهها بهصورت موازی بر روی خوشهای از کامپیوترها بسیار مناسب است. نگاشت-کاهش برای حل مشکلات محاسبات دادههای حجیم معرفی شده است که از قاعده تقسیم-غلبه پیروی میکند. مانند هر جای دیگر، مبحث زمان و زمانبندی در نگاشت-کاهش از اهمیت بسیار بالایی برخوردار است. بههمین دلیل در دهه اخیر الگوریتمهای زمانبندی متعددی در این زمینه تدارک یافته است. ایده اصلی این الگوریتمها افزایش نرخ محلیسازی داده، همزمانسازی، کاهش زمان پاسخ و زمان اتمام وظایف میباشد. اکثر این الگوریتمها تک هدفه میباشند و فقط یکی از موارد ذکر شده را مورد هدف قرار میدهند. الگوریتمهای چند هدفه موجود فقط بر روی یکی از فازهای اول یا دوم نگاشت-کاهش تمرکز دارند. در این مقاله، یک الگوریتم زمانبندی ترکیبی مبتنی بر اولویتبندی پویا کارها و محلیسازی داده در محیط نگاشت-کاهش به نام "HSMRPL" ارائه میشود که هدف اصلی آن افزایش نرخ محلیسازی داده و کاهش زمان محاسبات میباشد. در این الگوریتم از دو روش اولویتبندی پویا و شناسه محلیسازی استفاده میشود. برای ارزیابی الگوریتم پیشنهادی، آن را با الگوریتمهای پیشفرض هادوپ و به کمک محکهای استاندارد مقایسه کردیم. نتایج حاصله نشان میدهد که الگوریتم پیشنهادی ما نرخ محلیسازی را نسبت به الگوریتم FIFO، 5/18 درصد و نسبت به الگوریتم Fair، 4/10 درصد افزایش داده است. همچنین، الگوریتم پیشنهادی ما نسبت به الگوریتم FIFO، 8/3 درصد و نسبت به Fair، 4/13 درصد سریعتر است.
Nowadays, the Hadoop open-source project with the MapReduce framework has become very popular as it processes vast amounts of data in parallel on large clusters of commodity hardware in a reliable and fault-tolerant manner. MapReduce was introduced to solve large-data computational problems, and is dependent on the divide and conquer principle. Time and scheduling are always the most important aspects, hence in the past decades in the MapReduce environment, many scheduling algorithms have been proposed. The main ideas of these algorithms are increasing data locality rate, and decreasing response time and completion time. In this research we have proposed a new hybrid scheduling algorithm (HSMRPL) which uses dynamic job priority and identity localization techniques, and focuses on increasing data locality rate and decreasing completion time. We have evaluated and compared our algorithm with hadoop default schedulers by running concurrent workloads consisting of the WordCount and Terasort benchmarks. The results show that our proposed algorithm has increased the localization rate by 10.4% and 18.5% and the speed by 3.14% and 3.3% compared to the FIFO algorithm and the Fair algorithm respectively.