دانلود رایگان ترجمه مقاله الگوریتم زمان بندی پویا محدود شده بر اساس موعد مقرر با صرفه هزینه (نشریه IEEE 2015) (ترجمه رایگان – برنزی ⭐️)

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

A Cost-Effective Deadline-Constrained Dynamic Scheduling Algorithm for Scientific Workflows in a Cloud Environment

چکیده
1- مقدمه
2- معماری مد نظر برای اجرای جریان کاری در سیستم رایانش ابری
2-1 مدل برنامه ی کاربردی
2-2 مدل منابع ابری
2-3 مدل پلتفرم رایانشی

چکیده
رایانش ابری، که یک الگوی رایانش توزیع شده است، این امکان را فراهم می کند تا منابع IT بر روی اینترنت به کاربران ارائه شود و از مدل پرداخت هزینه به صورت آنی در زمان مصرف، استفاده می کند. برنامه ریزی و زمان بندی برای جریان های کاری چالش بر انگیز ترین مشکل در رایانش ابری می باشد. با وجود این که زمان بندی جریان کاری در سیستم های توزیع شده مانند شبکه ها و یا خوشه بندی ها به صورت گسترده مورد مطالعه قرار گرفته است، اما این راه حل ها برای رایانش ابری قابل استفاده نمی باشند. این موضوع به این علت است که محیط رایانش ابری نسبت به دیگر محیط های توزیع شده از دو منظر متفاوت می باشد : فراهم کردن منابع در زمان نیاز و مدل پرداخت آنی در زمان مصرف. ازین رو، برای به دست آوردن مزیت های واقعی محدودیت های جریان کاری بر روی منابع ابری، روش های جدید باید ایجاد شود که بتواند از مزیت های این رایانش ابری استفاده کرده و بتواند چالش های خاص آن را هم رفع کند. در این مطالعه، ما یک الگوریتم اکتشافی محدود شده از نظر موعد مقرر و مقرون به صرفه به صورت پویا را ارائه می کنیم که برای زمان بندی کردن جریان های کاری علمی در رایانش ابری عمومی مورد استفاده قرار می گیرد. هدف تکنیک پیشنهاد شده استفاده کردن از مزیت های ارائه شده توسط رایانش ابری و در عین حال در نظر داشتن عملکرد واقعی ماشین و تغییر در آن و تاخیر های اکتساب آنی برای شناسایی کردن زمان بندی های جریان کاری محدود به موعد مقرر با هزینه ی کمتر، می باشد. ارزیابی عملکردی بر روی بعضی از جریان های کاری شناخته شده نشان می دهد که الگوریتم پیشنهاد شده در مقایسه با جدید ترین الگوریتم های موجود در این زمینه، عملکرد بهتری دارد.
1- مقدمه
دانشمندان در دامنه های تحقیقاتی مختلف مانند فیزیک، بیو انفورماتیک ، علوم جغرافیایی و نجوم ، برنامه های علمی در مقیاس بزرگ و پیچیده را برای شبیه سازی کردن و تحلیل فعالیت های دنیای واقعی اجرا می کنند. بسیاری از این برنامه های بزرگ مقیاس معمولا به صورت جریان های کاری ساخته می شوند [1]. یک جریان کاری، یک برنامه ی کاربردی دانه درشت با تزویج ضعیف است که شامل وظایف محاسباتی می باشد که از طریق وابستگی های داده ها و کنترلی، به هم مرتبط شده اند. جریان های کاری علمی از نظر اندازه ممکن است از چند وظیفه با منابع محدود تا میلیون ها وظیفه نیازمند هزاران ساعت پردازش، ترابایت ها فضای ذخیره و منابع پهنای باند بسیار بالا باشند. این جریان های کاری پیچیده نیازمند محیط های محاسباتی با عملکرد بالا می باشند و معمولا باید وظایف موجود در این جریان های کاری بین گره های محاسباتی مختلف توزیع شود تا جریان کاری در یک زمان معقول، تمام شود. به صورت متداول، توسعه دهندگان برنامه های علمی از ایستگاه های کاری محلی، ابر کامپیوتر ها، دسته بندی ها و پلتفرم های شبکه ای برای اجرای این جریان های کاری استفاده می کنند. هر کدام از این پلتفرم ها توازن های مختلفی از نظر کارایی، عملکرد و هزینه ارائه می کنند. بسیاری از پروژه های شبکه ای مانند پگاسوس [2] ، آسکالون [3] و GrADS [4] سیستم های مدیریت جریان کاری را ارائه کرده اند تا جریان های کاری بر روی شبکه های تعریف، مدیریت و اجرا شود. رایانش ابری اخیرا به عنوان یکی از پلتفرم های مناسب برای اجرای این برنامه های علمی پیچیده ارائه شده است. بسیاری از مطالعه ها [5و6و7و8و9] به بررسی استفاده از رایانش ابری برای برنامه های علمی پرداخته اند و به این نتیجه رسیده اند که این سیستم های ابری می توانند از نظر عملکرد و هزینه، شرایط مناسبی را ایجاد کنند. اما با ظهور این الگوی محاسباتی جدید، روش های برنامه ریزی زمانی جدید که بتوانند از فواید سیستم های ابری استفاده کنند و چالش های خاص محیط های ابری را هم رفع کنند، در این قسمت مورد نیاز می باشد.
ابر ها می توانند مدل های محاسبه ی رایانش مبتنی بر کاربرد را ارائه کنند که این امکان را فراهم می کند تا منابع IT بر روی اینترنت تحویل داده شود و سپس از یک مدل پرداخت در زمان مصرف استفاده می کند که در این مدل، کاربر ها هزینه را بر اساس میزان مصرف از منابع پرداخت می کنند [11]. خدمات ابری در اصل به صورت زیر طبقه بندی می شوند : زیر ساختار ها به عنوان خدمات (IaaS) ، که شامل زیر ساختار های خام بوده و مرتبط با میان افزار ها می باشد ؛ پلتفرم ها به عنوان خدمات (PaaS) که شامل API ها برای توسعه ی برنامه ها بر روی یک پلتفرم انتزاعی می باشد و در نهایت دسته ی نرم افزار به عنوان خدمات (SaaS) که می تواند برای خدمات نرم افزا راه دور، پشتیبانی ایجاد کند. راه حل های مبتنی بر PaaS ها و SaaS ها در حال حاضر به عنوان جایگزین های ممکن برای اجرای جریان های کاری علمی در نظر گرفته نمی شوند. این موضوع به این دلیل است که راه حل های مبتنی بر PaaS شامل سر ریز اجرای برنامه های کاربردی موروثی می باشد در حالی که SaaS در حال حاضر به صورت پراکنده برای کاربرد در دسترس هستند [7]. سیستم های زیر ساخت ابری در مقابل، می توانند مزیت های مرتبط با هزینه و عملکرد مختلف را برای اجرای برنامه های علمی در مقایسه با محیط های اجرای توزیع شده ی متداول مانند شبکه ها و یا خوشه بندی ها ارائه کنند [ 6 و 10 ]. بعضی از فواید به صورت زیر می باشد.

Abstract

 Cloud Computing, a distributed computing paradigm, enables delivery of IT resources over the Internet and follows the pay-as-you-go billing model. Workflow scheduling is one of the most challenging problems in Cloud computing. Although, workflow scheduling on distributed systems like Grids and Clusters have been extensively studied, however, these solutions are not viable for a Cloud environment. It is because, a Cloud environment differs from other distributed environment in two major ways: on-demand resource provisioning and pay-as-you-go pricing model. Thus, to achieve the true benefits of workflow orchestration onto Cloud resources novel approaches that can capitalize the advantages and address the challenges specific to a Cloud environment needs to be developed. This work proposes a dynamic cost-effective deadline-constrained heuristic algorithm for scheduling a scientific workflow in a public Cloud. The proposed technique aims to exploit the advantages offered by Cloud computing while taking into account the virtual machine performance variability and instance acquisition delay to identify a just-in-time schedule of a deadline constrained scientific workflow at lesser costs. Performance evaluation on some well-known scientific workflows exhibit that the proposed algorithm delivers better performance in comparison to the current state-of-the-art heuristics.

1 INTRODUCTION

Scientists in different research domains such as physics, bio-informatics, earth science and astronomy run increasingly complex large scale scientific applications for simulation and analysis of the real-world activities. Many of such large scale applications are usually constructed as workflows [1]. A workflow is a loosely coupled coarse-grained parallel application that consists of a set of computational tasks linked through control and data dependencies. Scientific workflows may vary in size from a few tasks with limited resource needs to millions of tasks requiring tens of thousands of processing hours, terabytes of storage and high bandwidth network resources. Such complex workflows demand a high-performance computing environment and often it is desirable to distribute its tasks amongst multiple computing nodes in order to complete the work in a reasonable time. Traditionally, developers of scientific applications have used local workstations, supercomputers, clusters and grids platforms for running such workflows. Each of these platforms offer various trade-offs in terms of usability, performance and cost. Many Grid projects such as Pegasus [2], ASKALON [3] and GrADS [4] have designed workflow management systems to define, manage and execute workflows on the Grid. Cloud computing, has recently emerged as a promising execution platform for huge and complex scientific applications. Many studies [5], [6], [7], [8], [9], [10] have in of performance and cost. However, with the emergence of this new computing paradigm, novel scheduling approaches that are able to capitalize the advantages while addressing the challenges specific to a Cloud environment needs to be developed.

Cloud provides a utility-oriented computing model that enables delivery of IT resources over the Internet and follows the pay-as-you-go billing model where users are charged based on their resource consumption [11]. Cloud services are majorly categorized as: Infrastructure as a service (IaaS), which includes raw infrastructure and associated middleware; Platform as a service (PaaS), which includes APIs for developing applications on an abstract platform and Software as a service (SaaS) that provides support for remote software services. PaaS and SaaS based solutions are presently not considered as feasible alternatives for executing scientific workflows. This is because PaaS based solutions involve the overhead of porting legacy applications to new platforms whereas scientific computing SaaS services are currently rarely available for usage [7]. IaaS Cloud on the other hand, offers several cost and performance related benefits for executing scientific applications as compared to traditional distributed execution environments like grids and clusters [6], [10]. Some of these benefits are as follows..

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

A Cost-Effective Deadline-Constrained Dynamic Scheduling Algorithm for Scientific Workflows in a Cloud Environment