فهرست و منابع پایان نامه پیاده سازی الگوریتم FLB
فهرست:
فصل اول : مقدمه
1-1مفهوم گرید..................................................2
1-2طبقه بندی گرید............................................. 4
3-1 ارزیابی گرید............................................... 4
1-4کاربردگرید...................................................5
1-5 تعریف زمانبندی گرید........................................6
1-6 مروری بر تحقیقات گذشته......................................7
1-7 مفهوم اصطلاحات به کار برده شده..............................8
1-8 نمای کلی پایان نامه.........................................9
فصل دوم:زمانبندی کارها در سیستم های توزیع شده
2-1 زمانبندی کلاستر و ویژگیهای آن .............................. 10
2-2 زمانبندی گرید و ویژگیهای آن................................13
3-2 رده بندی الگوریتم های زمانبندی گرید....................... 16
2-3-1 زمانبندی محلی/سراسری................................. 16
2-3-2 زمانبندی ایستا/پویا...................................16
2-3-3 زمانبندی بهینه/نزدیک به بهینه...........................21
2-3-4 زمانبندی توزیع شده/مرکزی..............................22
2-3-5 زمانبندی همکار و مستقل...............................22
2-3-6 زمانبندی زمان کامپایل /اجرا........................ 23
2-4-1 رده بندی الگوریتم های زمانبندی از دیدگاهی دیگری..... 23
2-4-2 اهداف زمانبندی.........................................23
2-4-3 زمانبندی وفقی.......................................24
2-4-4 رده بندی برنامه های کاربردی...........................25
2-4-4-1 کارهای وابسته.....................................25
2-4-4-2 گراف کار..........................................26
2-4-5 وابستگی کارهای تشکیل دهنده برنامه کاربردی........... 26
2-4-6 زمانبندی تحت قیود کیفیت سرویس..........................26
2-4-7 راهکارهای مقابله با پویایی گرید.......................28
2-5 الگوریتم های زمانبندی کارهای مستقل......................32
2 -5-1 الگوریتم MET ...........................................32
2-5-2 الگوریتم MCT ..............................................32
2-5-3 الگوریتم Min-min...............................................33
2-5-4 الگوریتم Max-Min ................................................33
2 -5-5 الگوریتم Xsuffrage ..............................................34
2 -5-6- الگوریتم GA . ...........................................35
2-5-7- الگوریتم SA. ...........................................37
فصل سوم:الگوریتم های زمانبندی گراف برنامه
3-1 مشکلات زمانبندی گراف برنامه.................................39
3-2 تکنیکهای مهم زمانبندی گراف برنامه در سیستمهای توزیع شده.....40
3-2-1- روش ابتکاری بر پایه لیست ................................ 40
3-2-2- روش ابتکاری بر پایه تکثیر................................40
3-2-3- روش ابتکاری کلاسترینگ......................................41
3-3- دسته بندی الگوریتمهای زمانبندی گراف برنامه در سیستمهای توزیع شده.....................................................44
3-4- پارامترها و مفاهیم مورد استفاده در الگوریتمهای زمانبندی گراف برنامه.........................................................46
3-5- الگوریتمهای زمانبندی گراف برنامه با فرضیات محدودکننده......50
3-5-1- الگوریتمی با زمان چند جملهای برای گراف های درختی - الگوریتم HU ....................................................50
3-5-2- الگوریتمی برای زمانبندی گراف برنامه با ساختار دلخواه در سیستمی با دو پردازنده..........................................51
3-5-3- الگوریتمی برای زمانبندی گراف بازهای مرتب شده............52
3-6- الگوریتمهای زمانبندی گراف برنامه در محیطهای همگن ..........54
3-6-1- الگوریتم Sarkar................................................54
3-6-2- الگوریتمHLFET................................................55
3-6-3- الگوریتم ETF................................................55
3-6-4- الگوریتم ISH ..............................................55
3-6-5- الگوریتم FLB................................................56
3-6-6- الگوریتم DSC................................................56
3-6-7- الگوریتم CASS-II..............................................58
3-6-8- الگوریتم DCP................................................59
3-6-9- الگوریتم MCP................................................60
3-6-10- الگوریتم MD...............................................61
3-6-11- الگوریتم TDS...............................................61
3-7- الگوریتمهای زمانبندی گراف برنامه در محیطهای ناهمگن...............63
3-7-1- الگوریتم HEFT................................................63
3-7-2- الگوریتم CPOP..................................................63
3-7-3- الگوریتم LMT.................................................64
3-7-4- الگوریتمTANH .................................................65
فصل چهارم :الگوریتم FLB
1-4 ویژگیهای الگوریتم........................................66
4-2 اصطلاحات به کار برده شده.................................66
4-3 الگوریتم................................................67
4-4 پیچیدگی الگوریتم........................................75
4-5 کارایی الگوریتم.........................................77 .
فصل پنجم: شبیه سازی گرید
5-1 ابزار شبیه سازی...................................79
5-1-1- optosim..................................................79
5-1-2 SimGrid ..................................................80
5-1-3- Gridsim ..................................................80
کارهای انجام شده...............................................83 پیشنهادات............................................................83
مراجع .............................................................85
.
منبع:
[1] A. Darte. Two heuristics for task scheduling, laboratoire lip-imag, ecole normale
superieure de lyon, 69364. 1991.
[2] A. Radulescu and A. J. C. van Gemund. Flb: Fast load balancing for
distributed-memory machines. In Proc. Int’l Conf. on Parallel Processing, 1999.
[3] A. R˘adulescu and A. J. C. van Gemund. On the complexity
of list scheduling algorithms for distributed-memory
systems. In Proc. ICS, pages 68–75, June 1999.
[4] Amstrong, R., Hensgen, D., and Kidd, T. (1998). The relative performance of various
mapping algorithms is independent of sizable variances in run-time predictions.
IEEE Heterogeneous Computing Workshop(HCW’98), pages 79–87.
[5] Aubin Jarry, Henri Casanova, and Francine Berman. Dagsim: A simulator for
dag scheduling algorithms. Technical Report RR2000-46, LIP, 2000.
[6] Beaumont, O., Legrand, A., Marchal, L., and Robert, Y. (2005). Independent and
divisible tasks scheduling on heterogeneous star-shaped platforms with limited
memory. Proceedings of the Conference on Parallel,Distributed and Network-
Based Processing(Euromicro-PDP’05), pages 179–186.
[7] Braun, T., Siegel, H., Beck, N., and Freund, R. (2001). A comparision of eleven static
heuristics formapping a class of independent tasks onto heterogeneous distributed
computing systems. Journal of Parallel and Distributed Computing, 61:810–837.
[8] Casavant, T. and Kuhl, J. (1988). A taxonomy of scheduling in general-purpose
distributed computing systems. IEEE Transactions on Software Engineering,
14(2):141–153.
[9] C.A. Glass, C.N. Potts, and P. Shade. Unrelated parallel machine scheduling
using local search. Mathematical and Computer Modelling, 20(2):41–52, July
1994.
[10 ] D.K. Friesen. Tighter bounds for lpt scheduling on uniform processors. SIAM
Journal on Computing, 16(3):554–560, June 1987.
[11] Eckart Lorenz and the MAGIC collaboration. Status of the 17m diameter magic
telescope. New Astronomy Reviews, 48(5-6):339–344, April 2004.
[12] E.G. Coffman. Computer and Job-Shop Scheduling Theory. Wiley, 1976.
[13] E.G. Coffman and R.L. Graham. Optimal scheduling for two-processor systems.
Acta Informatica, 1:200–213, 1972.
[14] EGEE Project. http://public.eu-egee.org/.
[15] F. Berman, R.Wolski, H. Casanova,W. Cirne, H. Dail, M. Faerman, S. Figueira,
J. Hayes, G. Obertelli, J. Schopf, G. Shao, S. Smallen, S. Spring, A. Su, and
D. Zagorodnov. Adaptive computing on the grid using apples. IEEE Trans. on
Parallel and Distributed Systems (TPDS), 14(4):369–382, 2003.
[16] F.D. Berman, R. Wolski, S. Figueira, J. Schopf, and G. Shao. Applicationlevel
scheduling on distributed heterogeneous networks. In ACM Press, editor,
Proceedings of the 1996 ACM/IEEE conference on Supercomputing,, 1996.
[17] GridSim (2002). The gridsim project homepage. http://www.gridbus.org/gridsim/.
[18] H. El-Rewini and T.G. Lewis. Scheduling parallel program tasks onto arbitrary
target machines. Journal of Parallel and Distributed Computing, 9:138–153,
1990.
[19] Ibarra, O. and Kim, C. (1977). Heuristic algorithms for scheduling independent tasks
on non-identical processors. Journal of the ACM, 24(2):280–289.
[20] I. Foster and C. Kesselman. Globus: A metacomputing infrastructure toolkit.
Intl. J. Supercomputer Application, 11(2):115–128, 1997.
[21] I. Foster and C. Kesselman. The Grid: Blueprint for a New Computing Infrastructure.
Morgan Kaufmann, San Francisco, CA, 1998.
[22] I. Foster, J. Geisler, W. Nickless, W. Smith, and S. Tuecke. Software infrastructure
for the i-way high performance distributed computing experiment. In
Proc. 5th IEEE Symposium on High Performance Distributed Computing, pages
562–571, 1997.
[23] J. J. Hwang, Y. C. Chow, F. D. Anger, and C. Y. Lee. Scheduling precedence
graphs in systems with interprocessor communication times. SIAM Journal on
Computing, 18(2):244–257, April 1989.
[24] Jing-Chiou Liou and Michael A. Palis. An efficient task clustering heuristic for
scheduling dags on multiprocessors. In Symposium of Parallel and Distributed
Processing, 1996.
[25] Manzur Murshed Gippsland, Rajkumar Buyya , “Using the GridSim ToolKit for
Enabling Grid Computing Education”.
[26] M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the
Theory of NP-Completeness. W.H. Freeman and Company, 1979.
[27] M. Maheswaran and H. J. Siegel. A dynamic matching and scheduling algorithm
for heterogeneous computing system. In the 7th Heterogeneous Computing
Workshop(HCW ’98), pages 57–69. IEEE Computer Society Press, March 1998.
[28] N. Tonellotto, Information Science and Technologies Institute Italian National
Research Council Italy, R. Yahyapour Institute for Robotics Research University of
Dortmund Germany, “A Proposal for a Generic Grid Scheduling Architecture”.
[29] O. Ibarra and C. Kim. Heuristic algorithms for scheduling independent tasks
on nonidentical processors. Journal of the ACM, 77(2):280–289, April 1977.
[30] Pam, M. (1988). Software pipelining:an effective scheduling technique for vliw machines.
In Proceedings of the SIGPLAN’88, pages 318–328.
[31 ] P.C. Fishburn. Interval Orders and Interval Graphs. John Wiley & Sons, 1985.
[32] R.L. Graham. Bounds on multiprocessing timing anomalies. SIAM J. Appl.
Math., 17:416–429, 1969.
[33] R.L. Graham, E.L. Lawler, J.K. Lenstra, and A.H.G. Rinnoy Kan. Optimization
and approximation in deterministic sequencing and scheduling: A survey.
Annals of Discrete Mathematics, (5):287–326, 1979.
[34] S. J. Kim and J. C. Browne. A general approach to mapping of parallel computation
upon multiprocessor architectures. Proc. Int’l. Conf. on Parallel Processing,
pages 1–8, 1998.
[35] R. Sethi. Scheduling graphs on two processors. SIAM Journal of Computing,
5(1):73–82, March 1976.
[36] T. Adam, K.M. Chandy, and J.R. Dickson. A comparison of list schedules for
parallel processing systems. CACM, 17(12):685–690, 1974.
[37] T.C. Hu. Parallel sequencing and assembly line problems. Oper. Research,
19(6):841–848, November 1961
[38] T. Yang and A. Gerasoulis. Dsc: Scheduling parallel tasks on an unbounded
number of processors. IEEE Transactions on Parallel and Distributed Systems,
5(9):951–967, September 1994.
[39] W.H. Kohler and K. Steiglitz. Characterization and theoretical comparison of
branch-and-bound algorithms for permutation problems. Journal of the ACM,
21(1):140–156, January 1974
[40] Yu-Kwong Kwok and Ishfaq Ahmad. Static scheduling algorithms for allocating
directed task graphs to multiprocessors. ACM Computing Surveys, 31(4):406–
471, 1999.
[41] Eclipse Project, http://www.eclipse.org/eclipse/
[42] FAFNER. http://www.npac.syr.edu/factoring.html.
.