Abstract
Grid computing is hardware and software infrastructure which offers a cheap, distributable, coordinated and reliable access to powerful computational capabilities. To achieve the promising potentials of tremendous distributed resources, effective and efficient scheduling algorithms are fundamentally important. Most of the applications in grid computing fall into interdependent task model called workflow application. Task scheduling is a fundamental issue in achieving high performance in grid computing systems. It is well known that the complexity of a general scheduling problem is NP-Complete [1]. The grid workflow task scheduling problem is described by a Directed Acyclic Graph (DAG) or task graph. The graph represents the dependency among tasks, their computation time and communication time between them. In the management of workflow execution scheduling, the key issues that impact on the performance of the system is based on proper scheduling. In this paper, a new algorithm, named Minimum Makespan Grid Workflow Scheduling (MMGWS) is proposed to minimize makespan by reserving the resources in advance and schedule the task on priority. The proposed algorithm has been implemented for arbitrary task graphs in a simulated environment. Finally, the results are compared with the well known Min-Min and HEFT scheduling algorithms and showing that the proposed algorithm is yielding better results, that is, minimizing makespan
چکیده
محاسبات شبکه، یک زیرساخت نرم افزاری و سخت افزاری است که دسترسیِ ارزان، قابل توزیع، متناسب و معتبر را به قابلیت های قدرتمند محاسباتی فراهم می نماید. جهت نیل به پتانسیل های محتملِ منابع توزیعیِ عظیم، الگوریتم های زمان بندیِ موثر و کارآمد، دارای اهمیتی اساسی می باشند. اکثر برنامه های کاربردی در محاسباتِ شبکه، در ردۀ مدلِ وظیفۀ مستقلی به نام برنامۀ رویۀ کاری واقع می شوند. زمان بندیِ وظیفه مسئله ای اساسی در دستیابی به عملکرد عالی در سیستم های محاسباتی شبکه می باشد. بخوبی می دانیم که پیچیدگیِ یک مسئله زمان بندیِ عمومی، ان پیِ کامل است. مسئله زمان بندیِ وظیفه جریان رویۀ کاریِ شبکه توسط گراف جهت دارِ بی دور (DAG) یا گراف وظیفه توصیف می شود. این گراف وابستگیِ میان وظایف، زمان محاسباتیِ آنها و زمان ارتباط بین آنها را نشان می دهد. در مدیریت زمان بندیِ اجرایِ جریان کاری، مسئله کلیدی ای که برروی عملکرد سیستم تاثیر گذار است، زمان بندیِ صحیح است. در این مقاله، الگوریتمی جدید، به نام زمان بندی جریان کاری شبکه ای با حداقل زمان (MMGWS) جهت کمینه سازیِ زمان با حفظ منابعِ ازپیش موجود و زمان بندیِ کار طبق یک اولویت مطرح شده است. الگوریتم پیشنهادی برای گراف های اختیاریِ کار، در یک محیط شبیه سازی شده، پیاده و اجرا شدند. نهایتاً نتایج با الگوریتم های زمان بندیِ معروفِ Min-Min و HEFT مقایسه شدند و این طور برآمد که الگوریتم پیشنهادی به نتایج بهتری دست یافت که همان کمینه سازیِ زمان کل می باشد.
1-مقدمه
شبکه، کامپیوترها، پایگاه های داده، دستگاه ها، و مردم را در یک وب یکپارچه با هم مرتبط می سازد، و از مفاهیم کاربردیِ محاسباتی ازقبیل فرامحاسباتِ توزیع یافته، دستگاه های هوشمند و داده کاوی پشتیبانی میکند. پژوهش دربارۀ این مباحث منجر به ظهورِ یک الگوی جدید به نام محاسباتِ شبکه ای شده است. جهت نیل به پتانسیل محتملِ تعداد فراوانِ منابعِ توزیع یافته، الگوریتم های زمان بندیِ موثر و کارآمد بسیار ضروری و لازم هستند. تکنولوژیِ جریان کاری جهت اتخاذ و خودکار کردنِ فرایندی علمی مورد استفاده قرار گرفته اند که به دانشمندان در اجرای کارشان در محیط شبکه ای کمک می کند. برای اجرای جریان کاریِ علمی در شبکه، امور موجود در یک جریان کاری نیازمند این است که با منابع تخصیص داده شوند...