فرمت فایل | word, pdf |
---|
زمانبندی ایستای وظایف در محیط گرید محاسباتی با استفاده از ترکیب الگوریتمهای ژنتیک و پرندگان
چکیده
گريد محاسباتی مجموعهای از منابع و امکانات تحت پوشش یک شبکه کامپیوتری است. این سیستم بصورت جغرافیایی پراکنده شده و تحت مدیریت سازمانهای مختلف است. منابع يک گريد محاسباتی، پويا و در دامنههای مديريتی مختلفی قرار دارند. بنابراين زمانبندی کارها و مديريت منابع، موضوعات حياتی در گريد محاسباتی هستند. طبيعت پويا و ناهمگن منابع گريد و همچنين نيازهای مختلف برنامههای کاربردی روی آن، باعث پيچيدگي فرآیندی زمانبندی ميشود. براي مديريت چنين سيستم پيچيدهاي، نميتوان از رويكردهاي متداول مديريت منابع كه سعي ميكنند كارايي را در كل سيستم بهينه كنند، اسـتفاده كرد. بنابراین تاکـنون روشهای متفاوت زيادی برای حل اين مسئله پيشنهاد شده است. در اين تحقيق، به بررسی گريد محاسباتی و تعداد زيادی از الگوريتمهای اکتشافی برای زمانبندی وظايف در این محيط میپردازيم. روش پیشنهادی بر پایه ترکیب دو الگوریتم بهینهسازی ازدحام ذرات و ژنتیک شکل گرفته است. برای شبیهسازی محیط گرید از ساختار ماتریس زمان مورد انتظار استفاده میشود. نتایج بدست آمده نشان میدهد که روش جدید کارایی بهتر و زمان پاسخ کمتری را ارئه میدهد.
کلمات کليدی:
گريد محاسباتی، زمانبندی، الگوریتم ژنتیک، بهینهسازی ازدحام ذرات
فهرست مطالب
فصل اول: بیان مسئله و کلیات تحقیق. 2
فصل دوم: پیشینه و ادبیات تحقیق. 10
2-3-1 تعريف آی.بی.ام از محاسبات گريد. 15
2-3-2 تعريف گلوبوس از گريد. 16
2-4 توانمندي هاي سیستم گريد. 16
2-4-1 استفاده بهینه از منابع. 17
2-4-2 موازي سازي پردازنده ها 18
2-4-3 منابع و سازمان هاي مجازي. 19
2-4-4 دسترسي به منابع اضافه 19
2-5-3 مديريت كنترل كار سيستم. 23
2-6-1 قلمروهاي مديريتي چندگانه و استقلال آنها 26
2-6-4 پويايي و انعطافپذيري. 27
2-6-6 ميانافزار هستهاي گرید. 27
2-6-7 ميانافزار سطح كاربر. 28
2-6-8 برنامههاي کاربردی گرید. 28
2-7-2 لايه پروتکلهای منبع و اتصال. 31
2-7-3 لايه سرویس های تجمعی. 31
2-7-4 لايه برنامه های کاربر. 32
2-8 مثال های عملی از سیستم های گرید. 32
فصل سوم: مفاهیم و کارهای مرتبط.. 35
3-2 مروری بر الگوریتمها و روشها 37
3-2-1 زمانبندی چند سطحی پویا 37
3-2-2 اختصاص سریعترین پردازنده به بزرگترین وظیفه 37
3-2-4 الگوریتم اجتماع مورچگان تعادلی. 38
3-2-5 الگوریتم ژنتیک در سیستم گرید. 39
3-2-6 سیستم مبتنی بر عامل برای مدیریت منابع. 40
3-2-7 روش پیوندی مورچگان به منظور زمانبندی وظایف مستقل. 41
3-2-8 در اختیار گرفتن منابع به کمک الگوریتم یادگیری تقویتی. 42
3-2-9 روش حراج دو طرفه پیوسته در پردازش گرید. 43
3-2-10 متا زمانبندها برای زمانبندی برنامههای موازی. 44
3-2-11 کلونی مورچگان به منظور زمانبندی پویای کارها در گرید. 49
3-3 تعريف رسمي زمانبندی درگريد. 50
3-3-1 مدل زمانبندی متمرکز. 52
3-3-2 مدل زمانبندی توزيع شده 54
3-3-3 مدل زمانبندی سلسله مراتبي. 56
فصل چهارم: الگوریتمهای زمانبندی. 59
4-4 معرفی الگوریتمهای اکتشافی. 67
4-4-1 الگوریتم توازن بار خوشبینانه 67
4-4-2 الگوریتم حداقل زمان اجرا 68
4-4-3 الگوریتم حداقل زمان تکمیل. 69
4-5 مقایسه الگوریتم های اکتشافی. 79
4-6 معرفی الگوریتمهای فرا اکتشافی. 81
4-6-2 الگوریتم شبیه سازی تبرید. 85
4-6-3 الگوریتم جستجوی ممنوعه 86
4-6-4 الگوریتم بهینهسازی ازدحام ذرات.. 87
فصل پنجم: روش پیشنهادی و ارزیابی نتایج. 92
5-4 الگوریتمهای فرا اکتشافی. 106
5-4-1 ترکیب الگوریتم ژنتیک و ازدحام ذرات.. 106
5-4-2 تنظیمات اولیه الگوریتمها 109
5-5 مقایسه کارایی الگوریتم های تکاملی. 116
فهرست شکلها
شکل 2-1: لايههای انتزاع مختلف از يک سيستم گريد 15
شکل 2-2: نحوه موازیسازی پردازندهها در سیستم گرید 18
شکل 2-3: منابع پراكنده به صورت يك سازمان مجازي واحد 19
شکل 2-4: سيستم گريد از ديد استفادهکنندگان 22
شکل 2-5: جایگاه ماژول GSI در گريد 23
شکل 2-6: موقعيت سرويسهاي MDS در گريد 24
شکل 2-7: موقعيت زمانبندها در گريد 24
شکل 2-8: موقعيت ماژول GASS در گريد 25
شکل 2-9: بخش مديريت منابع در گريد 26
شکل 2-10: اجزاي معماري چهار لايهاي گريد 29
شکل 2-11: لايههاي کلی معماري گريد 30
شکل 3-1: ساختار کلی زمانبند گرید 39
شکل 3-2: ساختار سیستم مبتنی بر عامل برای مدیریت منابع 40
شکل 3-3: ساختار درختی به منظور مدیریت منابع 41
شکل 3-4: زمانبندی کارها به صورت چند عامله در پردازش شبکهای 43
شکل 3-5: نحوه زمانبندی در روش FIFO 44
شکل 3-6: رابطه میان متا زمانبند و کاربر و زمانبندهای محلی 45
شکل 3-7: شِمای کلی متا زمانبندها 48
شکل 3-8: ساختار عمل زمانبندی در گريد (برنامه کاربردی و کارهای آن) 51
شکل 3-9: معماری مدل زمانبندی متمرکز 53
شکل 3-10: زمانبندی توزيع شده با ارتباط مستقيم 55
شکل 3-11: مدل زمانبندی توزيع شده با ارتباط غيرمستقيم 56
شکل 3-12: مدل زمانبندی سلسلهمراتبی 57
شکل 4-1: رویه ساخت ماتریس ETC 61
شکل 4-2: شبه کد الگوریتم توازن بار خوشبینانه 68
شکل 4-3: شبه کد الگوریتم حداقل زمان اجرا 69
شکل 4-4: شبه کد الگوریتم MCT 70
شکل 4-5: شبه کد الگوریتم Min-Min 71
شکل 4-6: شبه کد الگوریتم Min-Max 72
شکل 4-7: شبه کد الگوریتم سافریج 73
شکل 4-8: شبه کد الگوریتم WQ 75
شکل 4-9: شبه کد الگوریتم LJFR-SJFR 76
شکل 4-10: شبه کد الگوریتم Duplex 76
شکل 4-11: شبه کد الگوریتم Maxstd 77
شکل 4-12: شبه کد الگوریتم kPB 78
شکل 4-13: شبه کد الگوریتم ژنتیک 85
شکل 4-14: شبه کد الگوریتم جستجوی ممنوعه 87
شکل 4-15: شبه کد الگوریتم بهینهسازی ازدحام ذرات 89
شکل 4-16: فلوچارت الگوریتم بهینهسازی ازدحام ذرات 91
شکل 5-1: میانگین هندسی زمان اتمام کل برای محیطهای توزیع شده مختلف 101
شکل 5-2: میانگین هندسی زمان گردش وظایف برای محیطهای توزیع شده مختلف 102
شکل 5-3: میانگین مقادیر کارایی منابع برای محیطهای توزیع شده مختلف 105
شکل 5-4: فلوچارت الگوریتم ترکیبی پیشنهادی 107
شکل 5-5: قسمتی از کروموزم مورد استفاده برای الگوریتمهای تکاملی 110
شکل 5-6: زمان اتمام کل برای حالات مختلف به واحد ثانیه 112
شکل 5-7: زمان گردش وظایف برای حالات مختلف به واحد ثانیه 114
شکل 5-8: درصد کارایی منابع در الگوریتمها و محیطهای مختلف 115
شکل 5-9: مقایسۀ سرعت همگرایی الگوریتمهای تکاملی مختلف 118
فهرست جداول
جدول 4-1: مقادیر پیشنهادی برای و 62
جدول 4-2: یک نمونه ماتریس با مقادیر و پایین 62
جدول 4-3: ماتریس ETC ناسازگار، ناهمگنی وظایف و ماشینها بالا 64
جدول 4-4: ماتریس ETC سازگار، ناهمگنی وظایف پایین، ناهمگنی ماشینها بالا 65
جدول 4-5: ماتریس ETC سازگار جزئی، ناهمگنی وظایف و ماشینها پایین 65
جدول 4-6: مقایسه الگوریتمهای اکتشافی 80
جدول 4-7: نگاهی به آخرین کارهای مرتبط 83
جدول 5-1: پارامترهای مدل براون و همکاران 95
جدول 5-2: چند حالت مختلف از یک محیط توزیع شده 97
جدول 5-3: زمان اجرای الگوریتمهای زمانبندی مختلف 98
جدول 5-4: زمان اتمام کل برای الگوریتمها و حالات مختلف محیط 99
جدول 5-5: زمان گردش وظایف برای الگوریتمها و حالات مختلف محیط 102
جدول 5-6: میزان کارایی منابع برای الگوریتمها و حالات مختلف محیط 103
جدول 5-7: توضیح پارامترهای الگوریتم ترکیبی پیشنهادی 109
جدول 5-8: تنظیمات اولیه مربوط به الگوریتمهای مورد استفاده 110
جدول 5-9: زمان اتمام کل الگوریتمها و حالات مختلف محیط گرید 111
جدول 5-10: زمان گردش وظایف الگوریتمها و حالات مختلف محیط گرید 113
جدول 5-11: درصد کارایی منابع برای الگوریتمها و حالات مختلف 115
جدول 5-12: توصیف توابع آزمون مختلف برای بررسی سرعت همگرایی 117
منابع فارسی
بدون منبع فارسی.
منابع انگلیسی
- Abraham, A., R. Buyya and B. Nath (2000). “Nature’s heuristics for scheduling jobs on computational grids”. The 8th IEEE international conference on advanced computing and communications (ADCOM 2000),pp. 45-52.
- Aggarwal, M., R. D. Kent and A. Ngom (2005(.“Genetic algorithm based scheduler for computational grids”. 19th International Symposium on High Performance Computing Systems and Applications, 2005. HPCS 2005. IEEE, pp. 209-215.
- Ali, S., H. J. Siegel, M. milanswaran, D. Hensgen and S. Ali (2000). “Modeling task execution time behavior in heterogeneous computing systems, Tamkang J”. Science and Engineering, Vol. 3, No. pp. 195-207.
- Berman, F., G. Fox and A. J. Hey (2003). “Grid computing: making the global infrastructure a reality”. John Wiley and sons.
- Bote-Lorenzo, M. L., Y. A. Dimitriadis and E. Gómez-Sánchez (2004). “Grid characteristics and uses: a grid definition”. Springer. pp. 291-298.
- Braunt, T. D., H. J. Siegel, N. Beck, L. L. Bölöni, M. Maheswaran, A. I. Reuther, J. P. Robertson, M. D. Theys, B. Yao and D. Hensgen (2001). “A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems”. Journal of Parallel and Distributed computing, Vol. 61, No. 6, pp. 810-837.
- Braunt, T. D., H. J. Siegel, N. Beck, L. L. Boloni, M. Maheswarans, A. I. Reuthert, J. P. Robertson, M. D. Theys, B. Yao and D. Hensgeno (2000). “A Comparison Study of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Ileterogeneous Distributed Computing Systems”. Vol. No. pp.
- Buyya, R. and K. Bubendorfer (2010). “Market-oriented grid and utility computing”. Wiley Online Library.
- Buyya, R. and M. Murshed (2002). “Gridsim: A toolkit for the modeling and simulation of distributed resource management and scheduling for grid computing”. Concurrency and computation: practice and experience, Vol. 14, No. pp. 1175-1220.
- Buyya, R., H. Stockinger, J. Giddy and D. Abramson (2001). “Economic models for management of resources in peer-to-peer and grid computing”. International Society for Optics and Photonics. pp.13-25.
- Buyya, R. and S. Venugopal (2004). “The gridbus toolkit for service oriented grid and utility computing: An overview and status report”. IEEE. pp. 19-66.
- Casavant, T. L. and J. G. Kuhl (1988). “A taxonomy of scheduling in general-purpose distributed computing systems”. IEEE Transactions on Software Engineering, Vol. 14, No. 2, pp. 141-154.
- Chauhan, P. (2014). “Decentralized Scheduling Algorithm for DAG Based Tasks on P2P Grid”. Journal of Engineering, Vol. 2014, No. 2, pp.
- Chen, W.-N. and J. Zhang (2009). “An ant colony optimization approach to a grid workflow scheduling problem with various QoS requirements”. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, Vol. 39, No. 1, pp. 29-43.
- Fayad, C., J. M. Garibaldi and D. Ouelhadj, (2007). “Fuzzy Grid Scheduling Using Tabu Search”. FUZZ-IEEE, pp. 1-6.
- Figueiredo, R. J., P. A. Dinda and J. A. Fortes (2003). “A case for grid computing on virtual machines”. IEEE. pp. 550-559.
- Foster, I. (2000). “Internet computing and the emerging grid”. nature web matters, Vol. 7, No. 1.
- Foster, I. and C. Kesselman (2003). “The Grid 2: Blueprint for a new computing infrastructure”. Elsevier.
- Foster, I., Y. Zhao, I. Raicu and S. Lu (2008). “Cloud computing and grid computing 360-degree compared”. IEEE. pp. 1-10.
- Fujimoto, N. and K. Hagihara (2004). “A comparison among grid scheduling algorithms for independent coarse-grained tasks”. IEEE, pp. 674-680.
- Gao, Y., H. Rong and J. Z. Huang (2005). “Adaptive grid job scheduling with genetic algorithms”. Future Generation Computer Systems, Vol. 21, No. 1, pp. 151-161.
- He, X., X. Sun and G. Von Laszewski (2003). “QoS guided min-min heuristic for grid task scheduling”. Journal of Computer Science and Technology, Vol. 18, No. 1, pp. 442-451.
- Kumar, V. and C. P. Katti (2014). “A Scheduling Approach with Processor and Network Heterogeneity for Grid Environment”. International Journal on Computer Science and Engineering (IJCSE). ISSN, Vol. No. 3, pp. 3975-3397.
- Legrand, A., L. Marchal and H. Casanova (2003). “Scheduling distributed applications: the simgrid simulation framework”. Proceedings of 3rd IEEE/ACM International Symposium on Cluster Computing and the Grid, 2003., IEEE. pp. 138-145.
- Maheswaran, M. and H. J. Siegel, (1998), “A dynamic matching and scheduling algorithm for heterogeneous computing systems”. Heterogeneous Computing Workshop, 1998. (HCW 98) Proceedings. pp. 57-69.
- Milani, F. S. and A. H. Navin (2015). “Multi-Objective Task Scheduling in the Cloud Computing based on the Patrice Swarm Optimization”. International Journal of Information Technology and Computer Science (IJITCS), Vol. 7, No. 5, pp. 61.
- Munir, E. U., J. Li, S. Shi, Z. Zou and D. Yang (2008). “MaxStd: A task scheduling heuristic for heterogeneous computing environment”. Information Technology Journal, Vol. 7, No. 4, pp. 679-683.
- Parsa, S. and R. Entezari-Maleki (2009). “RASA: A new task scheduling algorithm in grid environment”. World Applied sciences journal, Vol. 7, No. pp. 152-160.
- Rabiee, M. and H. Sajedi (2013). “Job scheduling in grid computing with cuckoo optimization algorithm”. International Journal of Computer Applications, Vol. 62, No. pp.
- Ramamritham, K., J. A. Stankovic and W. Zhao (1989). “Distributed scheduling of tasks with deadlines and resource requirements”. IEEE Transactions on Computers, Vol. 38, No. 8, pp. 1110-1123.
- Sadashiv, N. and S. D. Kumar (2011). “Cluster, grid and cloud computing: A detailed comparison”. IEEE. pp. 477-482.
- Schwiegelshohn, U., A. Tchernykh and R. Yahyapour (2008). “Online scheduling in grids”. IEEE, pp. 1-10.
- Shan, M.-C. and M. C. Murphy (1994). Method of automatically controlling the allocation of resources of a parallel processor computer system by calculating a minimum execution time of a task and scheduling subtasks against resources to execute the task in the minimum time, Google Patents.
- Shirazi, B., M. Wang and G. Pathak (1990). “Analysis and evaluation of heuristic methods for static task scheduling”. Journal of Parallel and Distributed Computing, Vol. 10, No. 3, pp. 222-232.
- Schwiegelshohn, U., R. M. Badia, M. Bubak, M. Danelutto, S. Dustdar, F. Gagliardi, A. Geiger, L. Hluchy, D. Kranzlmüller and E. Laure (2010). “Perspectives on grid computing”. Future Generation Computer Systems, Vol. 26, pp. 1104-1115.
- Wang, T., Z. Liu, Chen, Y. Xu and X. Dai (2014). “Load balancing task scheduling based on genetic algorithm in cloud computing”. 2014 IEEE 12th International Conference on Dependable, Autonomic and Secure Computing (DASC),, IEEE. pp. 146-152.
- Wang, J., Q. Duan, Y. Jiang and X. Zhu (2010). “A new algorithm for grid independent task schedule: genetic simulated annealing”. IEEE, pp. 165-171.
- Wang, Y., -M. Hu and Z.-X. Du (2006). “QoS-awared grid workflow schedule.”. Ruan Jian Xue Bao(Journal of Software), Vol. 17, No. 3, pp. 2341-2351.
- Wu, H., C.-Y. Lee, W.-Y. Chen and T.-Y. Lee (2007). “A Job Schedule Model Based on Grid Environment”. IEEEpp. 43-52.
- Xhafa, F. and A. Abraham (2008). “Meta-heuristics for grid scheduling problems”. Springer.
- Xhafa, F. and A. Abraham (2010). “Computational models and heuristic methods for Grid scheduling problems”. Future generation computer systems, Vol. 26, No. 4, pp 608-621.
- Xhafa, F., J. Carretero, L. Barolli and A. Durresi (2007). “Immediate mode scheduling in grid systems”. International Journal of Web and Grid Services, Vol. 3, No. 2, pp. 219-236.
- Xu, Z., X. Hou and J. Sun (2003). “Ant algorithm-based task scheduling in grid computing”. IEEEpp. 1107-1110.
- YarKhan, A. and J. J. Dongarra (2002). Experiments with scheduling using simulated annealing in a grid environment. Grid Computing-GRID 2002, chapter 3, Springer: 232-242.
- Yu, J. and R. Buyya (2005). “A taxonomy of scientific workflow systems for grid computing”. ACM Sigmod Record, Vol. 34, No. 3, pp. 44-49.
- Yu, Z. and W. Shi (2007). “An adaptive rescheduling strategy for grid workflow applications”. IEEEpp. 1-8.
محصولات مشابه
فرمت فایل | word, pdf |
---|---|
رشته | زبان و ادبیات فارسی |
تعداد صفحات | 141 |
سال | 1395 |