زمانبندی پویای دسته ای از کاهای با وظیفه موازی روی خوشه های ناهمگن

قیمت: 40,000 تومان

دانلود رایگان مقاله

خرید ترجمه مقاله

عنوان فارسی

زمانبندی پویای دسته ای از کاهای با وظیفه موازی روی خوشه های ناهمگن

عنوان لاتین

Dynamic scheduling of a batch of parallel task jobs on heterogeneous clusters

این مقاله به مسئله حداقل سازی طول زمانبندی دسته ای از کارها با زمان های ورود متفاوت می پردازد. یک کار با یک گراف بدون دور جهت دار (DAG) از وظایف موازی توصیف شده است. این مقاله یک متد زمانبندی پویا را پیشنهاد می کند که وقتی کارهای جدید ارائه می شود زمانبندی اتخاذ می شود و ممکن است پردازنده های اختصاص یافته به یک کار در طول اجرای آن تغییر کند. این متد زمانبندی به داخل یک استراتژی و الگوریتم زمانبندی تقسیم شده است. ما همچنین یک تطبیق از الگوریتم زمان اتمام زودتر ناهمگن (HEFT) پیشنهاد کردیم که در اینجا برای به کارگیری وظایف موازی در خوشه های ناهمگن با کارایی خوب بدون مصالحه makespan، P-HEFT نامیده می شود. نتایج مقایسه این الگوریتم با زمانبندی DAG دیگر با استفاده از یک شبیه سازی از چندین پیکربندی و انواع کارها نشان می دهد که P-HEFT یک makespan کوتاه تر برای یک DAG منفرد می دهد اما برای DAG چندگانه بدتر امتیاز دهی می کند. در نهایت نتایج زمانبندی پویا از یک دسته از کارها با استفاده از متد زمانبندی پیشنهادی بهبودهای قابل توجهی برای ماشین های بارگذاری شده سنگین تر نشان می دهد وقتی با منابع جایگزین و رویکرد رزرو مقایسه شده است.

This paper addresses the problem of minimizing the scheduling length (make-span) of a batch of jobs with different arrival times. A job is described by a direct acyclic graph (DAG) of parallel tasks. The paper proposes a dynamic scheduling method that adapts the schedule when new jobs are submitted and that may change the processors assigned to a job during its execution. The scheduling method is divided into a scheduling strategy and a scheduling algorithm. We also propose an adaptation of the Heterogeneous Earliest- Finish-Time (HEFT) algorithm, called here P-HEFT, to handle parallel tasks in heterogeneous clusters with good efficiency without compromising the makespan. The results of a comparison of this algorithm with another DAG scheduler using a simulation of several machine configurations and job types shows that P-HEFT gives a shorter makespan for a single DAG but scores worse for multiple DAGs. Finally, the results of the dynamic scheduling of a batch of jobs using the proposed scheduler method showed significant improvements for more heavily loaded machines when compared to the alternative resource reservation approach