نوع فایل: word
قابل ویرایش 85 صفحه
چکیده:
گرید محاسباتی مجموعه ای از منابع نا همگن و پویا که بوسیله یک شبکه به یکدیگر متصل می شوندو کاربران زیادی در مکان های مختلف آنها را به اشتراک می گذارند.اغلب برنامه های کاربردی بوسیله گراف جهت دار بدون سیکل خلاصه می شوندکه رئوس آن کارها و یالهای آن ارتباطات بین کارها را نشان می دهد. که در آن کارها وابسته هستند و بر اساس اولویت باید اجرا شوند به این معنی که در گراف تا والد یک کار انجام نشود فرزند یا فرزندان نباید انجام شوند.
برای اینکه تمام این اصول رعایت شود و از منابع به صورت بهینه استفاده گردد از الگوریتم های زمانبندی استفاده می کنیم.
در اینجا ما ابتدا به بررسی مفهوم گرید وفواید آن وسپس انواع زمانبندی در سیستم های توزیع شده و بررسی برخی از الگوریتم های زمانبندی در کارهای مستقل و وابسته می پردازیم و روشهای زمانبندی گراف برنامه وبعضی از الگوریتم های آنها در محیطهای ناهمگن وهمگن را معرفی می کنیم.سپس الگوریتمFLB راتشریح کردوشبیه ازهای گرید را بررسی می کنیم.
مقدمه:
قبل از ابداع کامپیوترهای شخصی، عملا سیستم های توزیع شده ای وجود نداشته است. در آن دوران ، استفاده از کامپیوتر، شامل نشستن پشت یک ترمینال و برقراری ارتباط با یک سیستم بزرگ بود. با اینکه ترمینال ها در چندین ساختمان و یا حتی محل فیزیکی قرار می گرفتند ، ولی عملا یک کامپیوتر مرکزی وجود داشت که مسئولیت انجام تمامی پردازش ها و ذخیره سازی داده ها را برعهده می گرفت.
Mainfram معایب
هزینه سیستم های Mainfarme. یکی از اولین دلایل مهم ، هزینه های بالای سیستم های Mainframe است. این مسئله از دو زاویه متفاوت قابل بررسی است: هزینه بالای سرمایه گذاری اولیه که بسیاری از سازمان ها و موسسات توان مالی آن را ندارند و دوم اینکه در این مدل ، دارای صرفا" یک نقطه آسیب پذیر با ریسک بالا می باشیم.
مالکیت اختصاصی داده ها. یکی از فاکتورهای مهم دیگر، سیاست های مربوط به مالکیت داده ها است. سازمان ها و موسسات که دارای داده های اختصاصی خود می باشند، علاقه مند به واگذاری مسئولیت مدیریت داده های مربوطه ، به سایر مکان های فیزیکی نمی باشند.
امنیت. یکی دیگر از فاکتورهای مهم در این زمینه موضوع امنیت است. برای یک سازمان ، اولا" دستیابی به اغلب داده های آن می بایست بسادگی محقق گردد و ثانیا" داده ها ی حساس موجود در سازمان می بایست از بعد امنیتی، ایمن نگهداری گردند. تامین دو خواسته فوق ( رویکردهای رقابتی و رویکردهای امنیتی ) با جدا سازی فیزیکی داده از یکدیگر محقق خواهد شد ( انباشت داده ها، با نگرش های متفاوت در رابطه با سرعت در دستیابی و ایمن در ذخیره سازی ، ضرورت وجود برنامه های توزیع شده را بخوبی نمایان می سازد )
مسائل فوق، ضرورت حرکت بسمت ایجاد یک الگوی جدید بمنظور طراحی برنامه های کامپیوتری را مطرح و بر همین اساس نسل جدیدی از برنامه های کامپیوتری با عنوان " برنامه های توزیع شده" در عرصه نرم افزار بوجود آمد.که این برنامه ها به سیستم های توزیع شده نیاز دارد.
یک برنامه توزیع شده، برنامه ای است که پتانسیل های پردازشی آن ممکن است توسط چندین کامپیوتر فیزیکی تامین و داده های آن در چندین محل فیزیکی، مستقر شده باشد.
یک سیستم توزیع شده مجموعه ای از کامپیوتر هاست که دارای منابع اجرایی مختلف و زیادی هستند.
فهرست مطالب:
1-1مفهوم گرید
1-2طبقه بندی گرید
3-1 ارزیابی گرید
1-4کاربردگرید
1-5 تعریف زمانبندی گرید
1-6 مروری بر تحقیقات گذشته
1-7 مفهوم اصطلاحات به کار برده شده
1-8 نمای کلی پایان نامه
فصل دوم:زمانبندی کارها در سیستم های توزیع شده
2-1 زمانبندی کلاستر و ویژگیهای آن
2-2 زمانبندی گرید و ویژگیهای آن
3-2 رده بندی الگوریتم های زمانبندی گرید
2-3-1 زمانبندی محلی/سراسری
2-3-2 زمانبندی ایستا/پویا
2-3-3 زمانبندی بهینه/نزدیک به بهینه
2-3-4 زمانبندی توزیع شده/مرکزی
2-3-5 زمانبندی همکار و مستقل
2-3-6 زمانبندی زمان کامپایل /اجرا
2-4-1 رده بندی الگوریتم های زمانبندی از دیدگاهی دیگری
2-4-2 اهداف زمانبندی
2-4-3 زمانبندی وفقی
2-4-4 رده بندی برنامه های کاربردی
2-4-4-1 کارهای وابسته
2-4-4-2 گراف کار
2-4-5 وابستگی کارهای تشکیل دهنده برنامه کاربردی
2-4-6 زمانبندی تحت قیود کیفیت سرویس
2-4-7 راهکارهای مقابله با پویایی گرید
2-5 الگوریتم های زمانبندی کارهای مستقل
2 -5-1 الگوریتم MET
2-5-2 الگوریتم MCT
2-5-3 الگوریتم Min-min
2-5-4 الگوریتم Max-Min
2-5-5 الگوریتم Xsuffrage
2 -5-6- الگوریتم GA
2-5-7- الگوریتم SA
فصل سوم:الگوریتم های زمانبندی گراف برنامه
3-1 مشکلات زمانبندی گراف برنامه
3-2 تکنیک های مهم زمان بندی گراف برنامه در سیستم های توزیع شده
3-2-1- روش ابتکاری بر پایه لیست
3-2-2- روش ابتکاری بر پایه تکثیر
3-2-3- روش ابتکاری کلاسترینگ
3-3- دسته بندی الگوریتم های زمان بندی گراف برنامه در سیستم های توزیع شده
3-4- پارامترها و مفاهیم مورد استفاده در الگوریتم های زمان بندی گراف برنامه
3-5- الگوریتم های زمان بندی گراف برنامه با فرضیات محدودکننده......50
3-5-1- الگوریتمی با زمان چند جمله ای برای گراف های درختی - الگوریتم HU
3-5-2- الگوریتمی برای زمان بندی گراف برنامه با ساختار دلخواه در سیستمی با دو پردازنده
3-5-3- الگوریتمی برای زمان بندی گراف بازه ای مرتب شده
3-6- الگوریتم های زمان بندی گراف برنامه در محیطهای همگن
3-6-1- الگوریتم Sarkar
3-6-2- الگوریتمHLFET
3-6-3- الگوریتم ETF
3-6-4- الگوریتم ISH
3-6-5- الگوریتم FLB
3-6-6- الگوریتم DSC
3-6-7- الگوریتم CASS-II
3-6-8- الگوریتم DCP
3-6-9- الگوریتم MCP
3-6-10- الگوریتم MD
3-6-11- الگوریتم TDS
3-7- الگوریتم های زمان بندی گراف برنامه در محیطهای ناهمگن
3-7-1- الگوریتم HEFT
3-7-2- الگوریتم CPOP
3-7-3- الگوریتم LMT
3-7-4- الگوریتمTANH
فصل چهارم:الگوریتم FLB
1-4 ویژگیهای الگوریتم
4-2 اصطلاحات به کار برده شده
4-3 الگوریتم
4-4 پیچیدگی الگوریتم
4-5 کارایی الگوریتم
فصل پنجم: شبیه سازی گرید
5-1 ابزار شبیه سازی
5-1-1- optosim
5-1-2 SimGrid
5-1-3- Gridsim
کارهای انجام شده
پیشنهادات
مراجع
فهرست اشکال:
شکل 1-2 ساختار کلاستر
شکل 2-2 ساختار زمانبند گرید
شکل 2-3-2 رده بندی الگوریتم های ایستا
شکل 2-4 رده بندی برنامه های کاربردی
شکل 2-5-6کلاس بندی برنامه های کاربردی
شکل 3-2-3 گراف نمونه با هزینه محاسباتی و ارتباطی
شکل 3-3 دسته بندی الگوریتم های گراف برنامه
شکل 3-4 گراف کارها
شکل 3-5-3 گراف بازه ای مرتب شده با هزینه محاسباتی یکسان
شکل 3-5-3 مقایسه الگوریتم های زمانبندی گراف برنامه در محیطهای
همگن
شکل 4-1 گراف کار
شکل 5-2 ساختار Gridsim
منابع ومأخذ:
[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
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
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
[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
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,
Hayes, G. Obertelli, J. Schopf, G. Shao, S. Smallen, S. Spring, A. Su, and
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,
[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.
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
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.
, 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.
پروژه پیاده سازی الگوریتم doc .FLB