زمانبندی مبتنی بر هزینه جریان‏‌های کاری با استفاده از ساختار جبری

نوع مقاله : مقاله پژوهشی

نویسندگان

1 گروه علوم کامپیوتر، دانشکده علوم، مرکز آموزش عالی محلات، محلات، ایران.

2 گروه مهندسی کامپیوتر، دانشکده برق و کامپیوتر، دانشگاه کاشان، کاشان، ایران.

چکیده

جریان‏‌های کاری یک مدل عمومی برای توصیف دامنه وسیعی از برنامه‏‌های کاربردی در سیستم‏‌های توزیع‌‏شده هستند. با توجه به قدرت محاسباتی رایانش ابری، از آن به طور گسترده برای حل جریان‏‌های کاری بزرگ استفاده می‏‌شود. زمانبندی جریان کاری در ابر در واقع یافتن منبع مناسب برای هر کار در جریان کاری به منظور ارضای برخی معیارهای کارایی مانند زمان اجرا و هزینه است. از آنجایی که زمانبندی یک مسئله زمان چندجمله‌ای غیرقطعی سخت (NP-complete) است، بسیاری از روش‏‌های ابتکاری برای سیستم‌‏های توزیع‌‏شده همگن و ناهمگن ارائه شده‌‏اند. مسیر بحرانی طولانی‌‏ترین مسیر یک جریان کاری است و زمان اجرای کلی جریان کاری به آن وابسته است. در واقع تاخیر در کارهای مسیر بحرانی می‌‏تواند زمان خاتمه جریان کاری را با تاخیر مواجه کرده و زمان انقضای جریان کاری را نقض کند. بر همین اساس در این مقاله، ما یک الگوریتم ابتکاری موازی برای زمانبندی جریان کاری مبتنی بر کیفیت سرویس ارائه می‌‏کنیم. تابع هدف این الگوریتم یک زمانبندی ایجاد می‏‌کند که هزینه اجرای یک جریان کاری را کمینه کرده، در حالی که زمان انقضای جریان کاری را نیز ارضا می‏‌کند. با اختصاص یک شبه مشبکه به هر زیرجریان کاری، زمان آغاز و پایان هر وظیفه و همچنین منبع مناسب برای آن مشخص می‌‏شود. نتایج حاصل از شبیه‌سازی بر روی جریان‌‏های کاری واقعی Montage و LIGO نشان می‏‌دهد که روش پیشنهادی در مقایسه با الگوریتم IC-PCP به میزان 5.5 درصد و نسبت به IC-PCPD2 به میزان 11 درصد هزینه را کاهش داده است.

کلیدواژه‌ها

عنوان مقاله [English]

Cost-based workflow scheduling using algebraic structures

نویسندگان [English]

  • Mohammad Javad Nadjafi-Arani 1
  • Saeed Doostali 2
1 Department of Computer Science, Faculty of Science, Mahallat Institute of Higher Education, Mahallat, Iran.
2 Department of Computer Engineering, Faculty of Electrical and Computer Engineering, Kashan University, Kashan, Iran.
چکیده [English]

Workflow is a common model for describing a wide range of applications in distributed systems. Due to the computing power of cloud computing, it has been widely applied to solve large workflows. Cloud workflow scheduling aims to find the most suitable resources for each task of a workflow so that optimizing certain performance metrics such as execution time and cost are met. Since scheduling is a well-known NP-complete problem, many heuristic approaches have been proposed to solve it in homogeneous and heterogeneous distributed systems. The longest path of a workflow is called the critical path on which the workflow completion time depends. In fact, delays in the execution of critical path tasks can delay the workflow completion time and violate the execution deadline of the workflow. Hence, in this paper, we present a parallel heuristic algorithm for quality-based workflow scheduling. The objective function proposed in the algorithm leads to minimizing the execution time of a workflow as well as respecting the deadline. By assigning a pseudo-lattice to each sub-workflow, the start and end time of each task and the appropriate resources for them are determined. The simulation results on the Montage and LIGO workflows show that the proposed approach reduces the cost by 5.5% compared to IC-PCP and by 11% compared to IC-PCPD2. 

کلیدواژه‌ها [English]

  • Workflow Scheduling
  • Cloud Computing
  • Critical Path
  • Partial Order Set
  • Lattice

مراجع

[1] Juve G., Chervenak A. L., Deelman E., Bharathi S., Mehta G., Vahi K., “Characterizing and profiling scientific workflows,” Future Generation Comp. Syst. vol. 29, no. 3, pp. 682-692, 2013.
[2] Arunarani A. R., Manjula D., Sugumaran V., “Task scheduling techniques in cloud computing: A literature survey,” Future Gener. Comput. Syst., vol. 91, pp. 407-415, 2019.
[3] Mershad K., Artail H., Saghir M. A. R., Hajj H., Awad M., “A study of the performance of a cloud datacenter server,” IEEE Transactions on Cloud Computing, vol. 5, no. 4, pp. 590-603, 2017.
[4] Sadooghi I., Martin J. H., Li T., Brandstatter K., Maheshwari K., de Lacerda Ruivo T. P. P., Garzoglio G., Timm S., Zhao Y., Raicu I., “Understanding the performance and potential of cloud computing for scientific applications,” IEEE Transactions on Cloud Computing, vol. 5, no. 2, pp. 358-371, 2017.
[5] Topcuoglu H., Hariri S., Wu M., “Performance-effective and low-complexity task scheduling for heterogeneous computing,” IEEE Trans. Parallel Distrib. Syst., vol. 13, no. 3, pp. 260-274, 2002.
[6] Son J. H., Kim J., Kim M., “Extracting the workflow critical path from the extended well-formed workflow schema,” J. Comput. Syst. Sci., vol. 70, no. 1, pp. 86-106, 2005.
[7] Abrishami S., Naghibzadeh M., Epema D. H. J., “Cost-Driven Scheduling of Grid Workflows Using Partial Critical Paths,” IEEE Trans. Parallel Distributed Syst., vol. 23, no. 8, pp. 1400-1414, 2012.
[8] Abrishami S., Naghibzadeh M., Epema D. H. J., “Deadline-constrained workflow scheduling algorithms for infrastructure as a service clouds,” Future Generation Comp. Syst., vol. 29, no. 1, pp. 158-169, 2013.
[9] Wu F., Wu Q., Tan Y., Li R., Wang W., “Pcp-b2: Partial critical path budget balanced scheduling algorithms for scientific workflow applications,” Future Generation Comp. Syst., vol. 60, pp. 22-34, 2016.
[10] Yuan Y., Li X., Wang Q., Zhu X., “Deadline division-based heuristic for cost optimization in workflow scheduling,” Inf. Sci., vol. 179, no. 15, pp. 2562-2575, 2009.
[11] Jailalita, Singh S., Dutta M., “Critical path based scheduling algorithm for workflow applications in cloud computing,” in: 2016 International Conference on Advances in Computing, Communication, Automation (ICACCA) (Spring), pp. 1-6, 2016.
[12] Calheiros R.N., Buyya R., “Meeting deadlines of scientific workflows in public clouds with tasks replication,” IEEE Trans. Parallel Distrib. Syst., vol. 25, no. 7, pp. 1787–1796, 2014.
[13] Cai Z., Li X., Gupta J. N. D., “Critical path-based iterative heuristic for workflow scheduling in utility and cloud computing,” in: Service-Oriented Computing - 11th International Conference, ICSOC 2013, Berlin, Germany, December 2-5, pp. 207-221, 2013.
[14] Poola D., Garg S. K., Buyya R., Yang Y., Ramamohanarao K., “Robust Scheduling of Scientific Workflows with Deadline and Budget Constraints in Clouds,” AINA, pp. 858-865, 2014.
[15] Arabnejad V., Bubendorfer K., Ng B., Chard K., “A deadline constrained critical path heuristic for cost-effectively scheduling workflows,” in: 2015 IEEE/ACM 8th International Conference on Utility and Cloud Computing (UCC), pp. 242-250, 2015.
[16] Arabnejad V., Bubendorfer K., Ng B., “Scheduling deadline constrained scientific workflows on dynamically provisioned cloud resources,” Future Generation Comp. Syst., vol. 75, pp. 348-364, 2017.
[17] Ghafouri R., Movaghar A., Mohsenzadeh M., “A budget constrained scheduling algorithm for executing workflow application in infrastructure as a service clouds,” Peer-to-Peer Netw. Appl., vol. 12, no. 1, pp. 241–268, 2019.
[18] Matani A., Darvishy A., “A Novel Critical-Path Based Scheduling Algorithm for Stochastic Workflow in Distributed Computing Systems,” in International Congress on High-Performance Computing and Big Data Analysis, pp. 476-489, 2019.
[19] Pan Y., Wang S., Wu L., Xia Y., Zheng W., Pang S., Zeng Z., Chen P., Li Y., “A Novel Approach to Scheduling Workflows Upon Cloud Resources with Fluctuating Performance,” Mob. Networks Appl., vol. 25, no. 2, pp. 690-700, 2020.
[20] Davey B. A., Priestley H. A., “Introduction to Lattices and Order,” Cambridge University Press, ISBN 978-0-521-78451-1, 2002.

فایل ها

سابقه مقاله

  • تاریخ دریافت: 12 شهریور 1399
  • تاریخ بازنگری: 27 خرداد 1400
  • تاریخ پذیرش: 23 شهریور 1400

هم رسانی

ارجاع به این مقاله

آمار