کوشا فایل

کوشا فایل بانک فایل ایران ، دانلود فایل و پروژه

کوشا فایل

کوشا فایل بانک فایل ایران ، دانلود فایل و پروژه

پروژه پیاده سازی الگوریتم doc .FLB

اختصاصی از کوشا فایل پروژه پیاده سازی الگوریتم doc .FLB دانلود با لینک مستقیم و پر سرعت .

پروژه پیاده سازی الگوریتم doc .FLB


پروژه پیاده سازی الگوریتم doc .FLB

 

 

 

 

 

 

نوع فایل: 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