پایان نامه بررسی الگوریتم های تخصیص مجدد در گرید های محاسباتی و ارائه یک الگوریتم کارا

فهرست:

- مقدمه .................................................................................................................................  1

   1-1 مقدمه................................................................................................................................................................... 1

   1-2 ضرورت اجرا....................................................................................................................................................... 2

   1-3 هدف از اجرای پایان­نامه.................................................................................................................................. 3

   1-4 مراحل انجام پایان­نامه...................................................................................................................................... 4      

   1-5 ساختار پایان­نامه........................................................................................................................................ 4

2- مفاهیم اولیه زمانبندی و مروری بر کارهای گذشته.................................................... 5

   2-1 مقدمه........................................................................................................................................................... 5

   2-2 ساختار متمرکز.......................................................................................................................................... 7

   2-3 ساختار غیر متمرکز و یا توزیعی.......................................................................................................... 8

   2-4 فرایند زمانبندی گرید و اجزای آن .................................................................................................... 10

   2-5 انواع زمانبند ............................................................................................................................................. 11

   2-6 انواع کارها ................................................................................................................................................. 12

   2-7 نحوه­ی زمانبندی ..................................................................................................................................... 14

   2-8 وظایف فرازمانبند .................................................................................................................................... 14

      2-8-1 نگاشت کار ...................................................................................................................................... 15

   2-9 گذری بر تحقیقات پیشین .................................................................................................................... 17

      2-9-1 مفاهیم اولیه ................................................................................................................................... 17

      2-9-2 الگوریتم ETF ................................................................................................................................ 19

      2-9-3 الگوریتم Myopic ......................................................................................................................... 19

      2-9-4 الگوریتم کمترین کمترین، بیشترین کمترین، حق رای ................................................... 19

      2-9-5 الگوریتم HLEFT ........................................................................................................................ 20

      2-9-6 الگوریتم hybrid ........................................................................................................................... 20

      2-9-7 الگوریتم GRASP ....................................................................................................................... 21

      2-9-8 الگوریتم CPOP ........................................................................................................................... 21

      2-9-9 الگوریتم PETS ............................................................................................................................. 22

      2-9-10 الگوریتم HLEFT با نگاه به جلو .......................................................................................... 23

      2-9-11 الگوریتم FTBAR .................................................................................................................... 23

      2-9-12  الگوریتم TSB .......................................................................................................................... 24

   2-10  جمع بندی ........................................................................................................................................... 24

3- الگوریتم­های پیشنهادی ............................................................................................ 25

   3-1 مقدمه ......................................................................................................................................................... 25

   3-2 الگوریتم Asuffrage .............................................................................................................................. 27

   3-3 الگوریتم MaxSuffrage ....................................................................................................................... 28

   3-4 الگوریتم DHLEFT................................................................................................................................ 30

4- نتایج حاصل از ارزیابی و مقایسه الگوریتم های پیشنهادی ....................................... 34

   4-1 مقدمه ......................................................................................................................................................... 34

   4-2 محک ارزیابی براون.................................................................................................................................. 34

   4-3 ارزیابی الگوریتم  Asuffrage............................................................................................................... 36

   4-4  ارزیابی الگوریتم  MaxSuffrage....................................................................................................... 38

   4-5  ارزیابی زمانبند الگوریتم پیشنهادی برای جریان کار.................................................................... 40

   4-6 ارزیابی الگوریتم DHLEFT.................................................................................................................. 43

   4-7 نتیجه گیری و پیشنهادات برای آینده .............................................................................................. 49

5- منابع........................................................................................................................... 50

منبع:

[1] Foster I., Kesselman C. and Tuecke S.  (2001), “The Anatomy of the Grid: Enabling Scalable Virtual Organizations”, International Journal of High Performance Computing applications, Vol. 15, No. 3, pp. 200-222.

[2] Lorpunmanee S., Sap M.N., Abdullah A.H. and Chompoo-inwai C. (2007), “An Ant Colony Optimization For Dynamic Job Scheduling In Grid Environment”, International Journal of Computer and Information Science and Engineering, Vol. 3, No. 1, PP. 207-214.

[3] Braun T.D., Siegel H.J., Beck N., Boloni L.L., Maheswaran M., Reuther A.L., Robertson J.P. and  Theys M.D., Yao B. (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.

[4] Sonmez O., Yigitbasi N., Iosup A., and Epema D. (2009), “Trace-Based Evaluation of Job Runtime and Queue Wait Time Predictions in Grids”, International Symposium on High Performance Distributed Computing (HPDC’09), Munich, Germany, June 11-13, PP. 111-120.

[5] Beltr´an M. and Guzm´an A. (2009), “The Impact of Workload Variability on Load Balancing Algorithms”, Scalable Computing: Practice and Experience, June, Vol. 10, No. 2, PP. 131–146.

[6] Fernández D. (1989), “Allocating Modules To Processors In A Distributed System”, IEEE Transactions on Software Engineering, Vol. 15, No. 11, PP. 1427-1436.

[7] Xhafa F., Abraham A. (2010), “Computational Models And Heuristic Methods For Grid Scheduling Problems”, Future Generation Computer Systems, Vol. 26, No. 4, PP. 608-621.

[8] Rodero I., Guim F., Corbalan J., Fong L., Sadjadi S. M. (2010), “Grid Broker Selection Strategies Using Aggregated Resource Information”, Future Generation Computer Systems, Vol. 26, No. 1, PP. 72-86.

[9] Zheng  R. and  Jin H. (2004), “An Integrated Management And Scheduling Scheme For Computational Grid”,  Second International Workshop on Grid and Cooperative Computing, Dec. 7-10, Shanghai China, PP. 48-56.

[10] Hamscher V., Schwiegelshohn U., Streit A., Yahyapour R. (2000), “Evaluation of Job-Scheduling Strategies for Grid Computing”, in Proc. of GRID 2000, First IEEE/ACM International Workshop, December 17-20, Bangalore, India, PP. 191-202.

[11] Schopf J. (2001), ‘Ten Actions When SuperScheduling’, document of Scheduling Working Group, Global Grid Forum, available on: http://www.ggf.org/documents/GFD.4.pdf.

[12] Czajkowski K., Fitzgerald S., Foster I., and Kesselman C. (2001), “Grid Information Services for Distributed Resource Sharing”, in Proc. the 10th IEEE International Symposium on High Performance Distributed Computing (HPDC-10), August 7-9, San Francisco, California, USA, PP. 181-194.

[13] Xhafa F. and Abraham A. (2010), “Computational models and heuristic methods for Grid scheduling problems,” Future generation computer systems, Vol. 26, No. 4, PP. 608-621.

[14] Yu J. and Buyya R. (2005), “A taxonomy of workflow management systems for grid computing”, Journal of Grid Computing, Vol. 3, No. 4, PP. 171-200.

[15]      Cao J., Jarvis S. A., Saini S. et al.( 2003), “Gridflow: Workflow management for grid computing”, in 3rd IEEE/ACM International Symposium on Cluster Computing and the Grid, Tokyo, Japan, PP. 198-205.

[16]      Zhang H.-b., Tang L.-s. and Liu L.-x. (2009), “Survey of grid scheduling”, Computer Engineering and Design, Vol. 9, PP. 026.

[17] Kwok 0Y. and Ahmed I. (1998). “Benchmarking the Task  Graph Scheduling Algorithms”.  Proc.  IPPS/SPDP.

 [18] Wieczorek M., Prodan R. and T. Fahringer (2005), “Scheduling of Scientific Workflows in the ASKALON Grid Enviornment”, ACM SIGMOD Record, 34(3):56-62.

[19] Maheswaran M. et al.(1999), “Dynamic Matching and Scheduling of a Class of Independent Tasks onto Heterogeneous Computng Systems”, The 8th Heterogeneous Computing Workshop (HCW'99), San Juan, Puerto Rico.

[20] Braun T. D., Siegel H. J. and Beck N.,( 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, 61:801-837.

[21] Topcuoglu H., Hariri S. and Wu M. Y. (2002), “Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing”, IEEE Transactions on Parallel and Distributed Systems, 13(3): 260-274.

[22] Yu, Z., & Shi, W. (2007, March), “An adaptive rescheduling strategy for grid workflow applications”, In Parallel and Distributed Processing Symposium, 2007. IPDPS. IEEE International (PP. 1-8). IEEE.

[23] Sakellariou R. and Zhao H. (2004), “A Hybrid Heuristic for DAG Scheduling on Heterogeneous Systems”, The 13th Heterogeneous Computing Workshop (HCW 2004), Santa Fe, New Mexico, USA, April 26.

[24] Feo T. A.and Resende M. G. C. (1995), “Greedy Randomized Adaptive Search Proce-dures”, Journal of Global Optimization, 6:109-133.

[25] Hoos H. H. and StÄutzle T. (2004), “Stochastic Local Search: Foundation and Applications”, Elsevier Science and Technology.

[26] Topcuoglu H., Hariri S. and Wu M.Y., (2002),  “Performance effective and low-complexity task  scheduling for heterogeneous computing”, IEEE  Trans. on Parallel and Distributed Systems, 13: 3.

[27] Topcuoglu H., Hariri, S. and Wu, M. Y. (2002), “Performance-effective and low-complexity task scheduling for heterogeneous computing”, Parallel and Distributed Systems, IEEE Transactions on, 13(3), 260-274

[28] Bittencourt, L. F., Sakellariou, R. and Madeira, E. R. (2010, February). “Dag scheduling using a lookahead variant of the heterogeneous earliest finish time algorithm”, In Parallel, Distributed and Network-Based Processing (PDP), 2010 18th Euromicro International Conference on (PP. 27-34). IEEE.

[29] Tabbaa, N., Entezari-Maleki, R. and Movaghar, A. (2011), “A Fault Tolerant Scheduling Algorithm for DAG Applications in Cluster Environments”, In Digital Information Processing and Communications (PP. 189-199). Springer Berlin Heidelberg.

[30] Ranjit R. (2012), “A Novel Approach for Task Scheduling in Multiprocessor System”, International Journal of Computer Applications (0975 – 8887) Vol. 44, No. 11, April;

[31] Yu J., Buyya R. and Ramamohanarao K. (2008), “Workflow scheduling algorithms for grid computing. In Metaheuristics for scheduling in distributed computing environments”, (PP. 173-214). Springer Berlin Heidelberg.

[32] https://github.com/frs69wq/daggen, (2013, November).

[33] Ali S., Siegel H. J., Maheswaran M. et al., “Representing task and machine heterogeneities for heterogeneous computing systems,” Tamkang Journal of Science and Engineering, Vol. 3, No. 3, PP. 195-208, 2000.