چکيده— تنوع و مقیاس اپلیکیشن های جریان کاری در حوزه های علمی و مهندسی، به تدریج افزایش یافته است. همزمان با این رشد، تلاش های بسیار زیادی به منظور ارتقای عملکرد این اپلیکیشن ها بواسطه استفاده از حجم زیادی از منابع در ابرهای با مقیاس بسیار بالا (hyper-scale) صورت گرفته است و البته موضوعی که در این بین کمتر مورد توجه قرار گرفته است؛ بحث "بازدهی منابع" می باشد. استفاده ناکارآمد از منابع در هنگام اجرای جریان های کاری علمی، ناشی از حجم فوق العاده منابع فراهم شده و نیز ناشی از اتلاف منابع بلا استفاده در جریان اجرای وظایف می باشد. ما در این مقاله، مساله زمانبندی جریان کاری با در نظر گرفتن بازدهی منابع را مورد بررسی قرار می دهیم. به این منظور، ما الگوریتم MER (حداکثر کاهش موثر و کارآمد) را ارائه می نماییم. این الگوریتم، یک راهکار برای بازدهی منابع می باشد که میزان استفاده از منابع در زمانبندی جریان کاری ایجاد شده توسط الگوریتم های زمانبندی جریان کاری را بهینه سازی می نماید. الگوریتم MER، حداقل افزایش در makespan (مجموع زمان انجام تمامی وظایف) را در ازای کاهش حداکثری استفاده از منابع حاصل می نماید که این فرآیند بواسطه یکپارچه سازی وظایف و نیز افزایش بهره وری از منابع ناکارآمد موجود در زمانبندی اولیه جریان کاری، انجام می شود. نوآوری اصلی در الگوریتم MER، بواسطه تعیین نقطه مصالحه و توازن "نزدیک به حالت بهینه" میان افزایش makespan و نیز کاهش استفاده از منابع، می باشد. یافتن چنین نقطه ای به لحاظ کاربردی بسیار مهم می باشد و می تواند به حصول مزایای زیر منجر شود: (1) بهبود استفاده از منابع، (2) کاهش نیاز به تامین منابع بیشتر، (3) صرفه جویی در مصرف انرژی. مورد مهم دیگری که در این کار تحقیقاتی به آن پرداخته می شود؛ مساله قابلیت کاربرد گسترده الگوریتم MER می باشد. اساسا می توان الگوریتم MER را در تمامی محیط هایی که با اجرای جریان های کاری (علمی) با حجم زیاد وظایف "مقید به اولویت" سروکار دارند، مورد استفاده قرار داد. با این حال بیشترین میزان تناسب و سازگاری الگوریتم MER با مدل ابر IaaS (سرویس زیر ساخت) است. با توجه به نتایج حاصل از شبیه سازی های جامع با استفاده از مسیرهای جریان کاری علمی، اثبات می کنیم که الگوریتم MER، می تواند باعث کاهش حجم استفاده از منابع به میزان 54% به ازای افزایش کمتر از 10 درصدی متوسط makespan شود. در ادامه قابلیت و کارایی الگوریتم MER با استفاده از نتایج (حاصل از مجموعه آزمایشات جامع با مقادیر متغیر حد تاخیر makespan) مورد بررسی قرار می گیرد. این نتایج نشان دهنده کاهش استفاده از منابع، افزایش مقدار makespan و نیز توازن میان آنها در اپلیکیشن های مختلف جریان کاری بواسطه استفاده از الگوریتم MER می باشند.
کلمات کليدي-رایانش ابری، جریان های کاری علمی، بازدهی منابع، مدیریت منابع، زمانبندی جریان کاری

Abstract:  Workflow applications in science and engineering have steadily increased in variety and scale. Coinciding with this increase has been the relentless effort to improve the performance of these applications through exploiting the abundance of resources in hyper-scale clouds and with little attention to resources efficiency. The inefficient use of resources when executing scientific workflows results from both the excessive amount of resources provisioned and the wastage from unused resources among task runs. In this paper, we address the problem of resource-efficient workflow scheduling. To this end, we present the Maximum Effective Reduction (MER) algorithm, a resource efficiency solution that optimizes the resource usage of a workflow schedule generated by any particular scheduling algorithm. MER trades the minimal makespan increase for the maximal resource usage reduction by consolidating tasks with the exploitation of resource inefficiency in the original workflow schedule. The main novelty of MER lies in its identification of “near-optimal” trade-off point between makespan increase and resource usage reduction. Finding such a point is of great practical importance and can lead to: (1) improvements in resource utilization, (2) reductions in resource provisioning, and (3) savings in energy consumption. Another significant contribution of this work is MER’s broad applicability. In essence, MER can be applied to any environments that deal with the execution of (scientific) workflows of many precedence-constrained tasks although MER best suits for the IaaS cloud model. Based on results obtained from our extensive simulations using scientific workflow traces, we demonstrate MER is capable of reducing the amount of actual resources used by 54% with an average makespan increase of less than 10%. The efficacy of MER is further verified by results (from a comprehensive set of experiments with varying makespan delay limits) that show the resource usage reduction, makespan increase and the trade-off between them for various workflow applications.
Keywords-Cloud computing; Scientific workflows; Resource efficiency; Resource management; Workflow scheduling