زمانبندی مبتنی بر هزینه جریانهای کاری با استفاده از ساختار جبری | ||
| محاسبات نرم | ||
| مقاله 8، دوره 9، شماره 2 - شماره پیاپی 18، اسفند 1399، صفحه 114-129 اصل مقاله (1.32 M) | ||
| نوع مقاله: مقاله پژوهشی | ||
| شناسه دیجیتال (DOI): 10.22052/scj.2021.242814.0 | ||
| نویسندگان | ||
| محمد جواد نجفی آرانی1؛ سعید دوست علی* 2 | ||
| 1گروه علوم کامپیوتر، دانشکده علوم، مرکز آموزش عالی محلات، محلات، ایران. | ||
| 2گروه مهندسی کامپیوتر، دانشکده برق و کامپیوتر، دانشگاه کاشان، کاشان، ایران. | ||
| چکیده | ||
| جریانهای کاری یک مدل عمومی برای توصیف دامنه وسیعی از برنامههای کاربردی در سیستمهای توزیعشده هستند. با توجه به قدرت محاسباتی رایانش ابری، از آن به طور گسترده برای حل جریانهای کاری بزرگ استفاده میشود. زمانبندی جریان کاری در ابر در واقع یافتن منبع مناسب برای هر کار در جریان کاری به منظور ارضای برخی معیارهای کارایی مانند زمان اجرا و هزینه است. از آنجایی که زمانبندی یک مسئله زمان چندجملهای غیرقطعی سخت (NP-complete) است، بسیاری از روشهای ابتکاری برای سیستمهای توزیعشده همگن و ناهمگن ارائه شدهاند. مسیر بحرانی طولانیترین مسیر یک جریان کاری است و زمان اجرای کلی جریان کاری به آن وابسته است. در واقع تاخیر در کارهای مسیر بحرانی میتواند زمان خاتمه جریان کاری را با تاخیر مواجه کرده و زمان انقضای جریان کاری را نقض کند. بر همین اساس در این مقاله، ما یک الگوریتم ابتکاری موازی برای زمانبندی جریان کاری مبتنی بر کیفیت سرویس ارائه میکنیم. تابع هدف این الگوریتم یک زمانبندی ایجاد میکند که هزینه اجرای یک جریان کاری را کمینه کرده، در حالی که زمان انقضای جریان کاری را نیز ارضا میکند. با اختصاص یک شبه مشبکه به هر زیرجریان کاری، زمان آغاز و پایان هر وظیفه و همچنین منبع مناسب برای آن مشخص میشود. نتایج حاصل از شبیهسازی بر روی جریانهای کاری واقعی Montage و LIGO نشان میدهد که روش پیشنهادی در مقایسه با الگوریتم IC-PCP به میزان 5.5 درصد و نسبت به IC-PCPD2 به میزان 11 درصد هزینه را کاهش داده است. | ||
| کلیدواژهها | ||
| زمانبندی جریان کاری؛ رایانش ابری؛ مسیر بحرانی؛ مجموعه مرتب جزئی؛ مشبکه | ||
| مراجع | ||
|
[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. | ||
|
آمار تعداد مشاهده مقاله: 11,214 تعداد دریافت فایل اصل مقاله: 1,812 |
||
