مقاله ارائه یک الگوریتم خوشه بندی برای توزیع مناسب کار و ارزیابی کارایی آن در word

 مقاله ارائه یک الگوریتم خوشه بندی برای توزیع مناسب کار و ارزیابی کارایی آن در word دارای 137 صفحه می باشد و دارای تنظیمات و فهرست کامل در microsoft word می باشد و آماده پرینت یا چاپ است

فایل ورد مقاله ارائه یک الگوریتم خوشه بندی برای توزیع مناسب کار و ارزیابی کارایی آن در word  کاملا فرمت بندی و تنظیم شده در استاندارد دانشگاه  و مراکز دولتی می باشد.

این پروژه توسط مرکز مرکز پروژه های دانشجویی آماده و تنظیم شده است

توجه : توضیحات زیر بخشی از متن اصلی می باشد که بدون قالب و فرمت بندی کپی شده است

بخشی از فهرست مطالب پروژه مقاله ارائه یک الگوریتم خوشه بندی برای توزیع مناسب کار و ارزیابی کارایی آن در word

مقدمه

فصل اول

مفاهیم اولیه

سیستم های توزیع شده

مزایا و معایب سیستم های توزیع شده

انگیزش;

مراحل کلی تبدیل برنامه ترتیبی به برنامه توزیع شده

ساختار پایان نامه

جمع بندی

فصل دوم

تکنیک ها و ابزارهای مرتبط

ابزارهای تبادل پیام در مقایسه با حافظه اشتراکی توزیع شده

تبادل پیام

خصوصیات مطلوب یک سیستم تبادل پیام

طبقه بندی ابزارهای تبادل پیام

توزیع گرهای اتوماتیک;

ابزار های نیمه اتوماتیک;

ابزار های تمام اتوماتیک;

توزیع بایت کد جاوا بر مبنای تحلیل وابستگی به صورت اتوماتیک;

مراحل کار الگوریتم

مطابقت اندازه گره در محیط برنامه نویسی شیگرا به صورت پویا توسط روش اسکوپ

افراز بندی در سیستم توزیع شده شی گرا به صورت پویا

معیارهای مختلف در زمینه گروه بندی اشیاء

الگوریتم خوشه بندی مشتق شده از الگوریتم حریصانه lo,s

دسته بندی اشیاء موجود در  خوشه ها

نتیجه گیری

فصل سوم

استخراج گراف فراخوانی

ساخت گراف جریان فراخوانی

الگوریتم های  تعین مقصد فراخوانی

روش آنالیز نوع ایستاتیک;

روش آنالیز سلسله مراتب کلاس;

روش آنالیز نوع سریع

روش آنالیز نوع سریع حساس به جریان برنامه

استخراج گراف فراخوانی جهت ساخت گراف کلاسها

مقایسه الگوریتم های ساخت گراف فراخوانی

وزن گذاری گراف فراخوانی

استراتژی وزن گذاری یال های گراف فراخوانی توابع

برآورد زمان اجرای کد های ترتیبی

روش های برآورد زمان اجرای کد های ترتیبی

برآورد زمان اجرای کدهای برنامه با آنالیز متن برنامه

تخمین ایستای زمان اجرای برنامه ها

پارامتر های ورودی

تعیین سرحد تکرار حلقهها و فراخوانیهای بازگشتی

حذف مسیرهای اجرا نشدنی

بهینه سازی کامپایلرها و تخمین زمان اجرای برنامه

زبان های برنامه سازی و تخمین زمان اجرا

رعایت میزان دقت تخمین در زمان اجرا

معیارهای موجود در تخمین طولانی ترین زمان اجرا

تحلیل جریان داده

تحلیل کاهش بازگشتی

حجم زیاد اطلاعات

استفاده از کد Object برنامه

بایت کد جاوا و محاسبه زمان اجرای دستورالعملها

محاسبه زمان اجرای حلقه ها

نحوه شناسایی حلقه های تکرار

انتشار دامنه مقادیر

دستورات شرطی و نحوه شناسایی آنها

محاسبه زمان اجرای کل برنامه با استفاده از روش پیشنهادی

تشخیص حلقه های تکرار

تخمین تعداد تکرار حلقه ها

انتشار مقادیر

محاسبه زمان اجرای توابع موجود در یک دور از گراف

یافتن نقاط همگام سازی

بررسی نتیجه الگوریتم پیشنهادی برروی یک برنامه نمونه

جمع بندی

فصل چهارم

خوشه بندی

مقدمه

خوشه بندی سلسله مراتبی

خوشه بندی سلسله مراتبی پایین به بالا (تلفیق)

روش های ادغام خوشه ها در خوشه بندی پایین به بالا

      Single Linkage

Complete Linkage

Group Avreage Linkage

 Simple Average Linkage

 Weighted Average Linkage

 سه روش مفید دیگر (Median, Centroid, Wards )

تکنیک های یافتن تعداد خوشه های بهینه

جدول تلفیق (جدول ادغام)

تراز تلفیق

 نمودار dendrogram

تعیین تعداد خوشه های بهینه

تکنیک های پیدا کردن نقطه پیچش در نمودار جدول تلفیق

روش پیشنهادی در این پایان نامه جهت خوشه بندی

الگوریتم پیشنهادی برای خوشه بندی کلاس ها

جمع بندی

فصل پنجم

پیاده سازی و ارزیــابــی

محیط پیاده سازی شده

مقایسه روش خوشه بندی پیشنهادی با روش حریصانه متداول

فصل ششم

نتیجـه‌گیـری

نتیجه گیری

کارهای آتی

منابع و مراجع

چکیده

 با توجه به تحولات اخیر در تکنولوژی ارتباطات و نیاز روز افزون به توان پردازشی زیاد ، امروزه تصور مجموعه ای از کامپیوتر ها که به صورت یک کامپیوتر یکپارچه ،اما با قدرت بسیار بیشتر در حال کار هستند چندان بعید نیست. یک برنامه توزیع شده  می تواند به صورت مجموعه ای از پردازه های در حال اجرا که با تبادل پیام از طریق شبکه ارتباطی با یکدیگر همکاری می کنند تعریف شود

 با این حال همواره بعنوان یک اصل، ساخت یک برنامه توزیع شده مشکلتر از برنامه متمرکز است. از جمله عواملی که باعث افزایش این پیچیدگی میشود مواجه شدن با برنامه نویسی تحت شبکه، همگام سازی پردازه ها، حل مساله انحصار متقابل بین آنها، افزایش تحمل پذیری خطا و اشکال زدایی میباشد. یکی از روش های مورد توجه در ساخت سیستم های توزیع شده، تبدیل اتوماتیک برنامه های ترتیبی به برنامه های توزیع شده است

   در این پایان نامه روشی جدید برای توزیع اتوماتیک برنامه های ترتیبی با خوشه بندی کلاس های آن صورت می گیرد.تکنیک های خوشه بندی متنوعی تا کنون برای این منظور استفاده شده است که پس از بررسی مزایا و معایب هر یک روش جدیدی برای خوشه بندی معرفی شده است. پس از خوشه بندی معماری طوری بازسازی میشود که حداکثر همروندی در اجرای قطعات توزیع شده ایجاد شود لذا در این پروژه روشی برای بازسازی معماری سیستم های توزیعی علمی با ایجاد حداکثر همروندی در اجرای کد برنامه ها ارائه خواهد شد

واژه‌های کلیدی

خوشه بندی ، چسبندگی ، توزیع شدگی

بخشی از منابع و مراجع پروژه مقاله ارائه یک الگوریتم خوشه بندی برای توزیع مناسب کار و ارزیابی کارایی آن در word

[1]     M. M. Fuad, M. J. Oudshoorn, “AdJava: Automatic Distribution of Java Applications”, the 25th Australasian Computer Science Conference,

[2]     I. Attali, D. Caromel, R. Guider, “A Step toward automatic distribution of java programs”, ACM-ISCOPE conference on Java Grande,

[3]     A. Spiegel, “Automatic Distribution of Object-Oriented Programs ”, PhD Thesis, FU Berlin, FB Mathematik und Informatik, December

[4]     S.Parsa, V.Khalilpoor, “Automatic Distribution of Sequential Code Using JavaSymphony Middleware”, 32nd International Conference On current Trends in Theory and Practice of Computer Science

[5]     S. Vijay, and H. Laurie, “Practical virtual methods call for java” Proc. of the Conf. on Object-  Oriented programming, systems, languages, and applications ,

[6]     H. Zima, “Super compilers for Parallel and Vector Computers” ACM Press,

[7]     D. Raysidey, S. Reussz, E. Hedgesy, and K. Kontogiannis, “The Effect of Call Graph Construction Algorithms for Object-Oriented Programs on Automatic Clustering” IEEE Computer Society   Washington, DC, USA, ISBN: 0-7695-0656-

[8]     D. Grove, G. DeFouw, J. Dean , and C. Chambers “Call Graph Construction in Object-Oriented Languages” Proc of the 12th ACM SIGPLAN conference on Object-oriented programming , Atlanta, Georgia, United States    October 05 – 09,

[9]     P. Puschner, A. Burns: Guest Editorial, “A Review of Worst-Case Execution-Time Analysis”, Journal of Real-Time Systems, 18(2/3):115–128, May

[10]  “The Java Virtual Machine Specification”, Sun Microsystems, Inc

[11]  C. A. Healy, M. Sjodin, D. B. Whalley, “Ounding Loop Iterations for Timing Analysis”, In Proc. IEEE Real-Time Technology and Aplications Symposium, pages 12–21, Jun

[12]  J. Gustafsson, “Analysing Execution-Time of Object-Oriented Programs using Abstract Interpretation”, PhD thesis, Uppsala University, Uppsala, Sweden, May

[13]  R. Kirner, “Extending Optimising Compilation to Support Worst-Case Execution Time Analysis”, PhD Thesis, Institut für Technische Informatik, Technischen Universitt Wien, May

[14]   L. Patcas, “Basic Timing and Control-Flow Analysis of Programs Written in Assembly Languages”, Diploma Thesis, Department of Computer and Software Engineering Politehnica University of Timisoara, June

[15]  R. Kirner, P. Puschner, “A Simple and Effective Fully Automatic Worst-Case Execution Time Analysis for Model-Based Application Development”, In Proc. Workshop on Intelligent Solutions in Embedded Systems,

[16]  A. Mok, “Evaluating tight execution time bounds of programs by annotations”, In Proc. 6th Workshop on Real-Time Operating Systems and Software, pages 74-80. IEEE, May

[17]  C. A. Healy, M. Sjodin, D. B. Whalley, “Ounding Loop Iterations for Timing Analysis”, In Proc. IEEE Real-Time Technology and Aplications Symposium, pages 12–21, Jun

[18]  C, A. Healy, “Automatic Utilization of Constraints for Timing Analysis”, PhD thesis, Florida State University, July

[19]  J. Gustafsson, “Analysing Execution-Time of Object-Oriented Programs using Abstract Interpretation”, PhD thesis, Uppsala University, Uppsala, Sweden, May

[20]  A. Ermedahl, F. Stappert, J. Engblom, “Clustered Worst-Case Execution-Time Calculation”, IEEE Transactions on Computers, Vol. 54, No. 9, September

[21]  C. Sandberg , A. Ermedahl , J. Gustafsson , B. Lisper, “Faster WCET flow analysis by program slicing”, ACM SIGPLAN Notices, v.41 n.7, July

[22]  P. Altenbernd, “On the false problem in hard real-time programs”, In Proc. 8th Euromicro Workshop on Real Time Systems, pages 102–107, L’Aquila,

[23]  P. Puschner, “Zeitanalyze von Echtzeitprogrammen”, PhD thesis, Technische Universitat, Institut fur Technische Informatik, Vienna, Austria,

[24]  Y. S. Li, S. Malik, “Performance Analysis of embedded Software Using Implicit Path Enumeration”, In Proc. 32nd ACM/IEEE Design Automation Conference, pages 456–461, Jun

[25]  M. Schoeberl, “A time predictable Java processor”, In Proceedings of the Design, Automation and Test in Europe Conference, pages 800–805, Munich, Germany, March

[26]  R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, F. K. Zadeck, “Efficiently Computing Static Single Assignment Form and the Control Dependence Graph ”, ACM Transactions on Programming Languages and Systems, 13(4):451–490, October

[27]  C. S. Ananian, “Harpoon Project Compiler Intermediate Representation”, October 12, 1998, www.flex-compiler.lcs.mit.edu/Harpoon/quads/quads.htm

[28]  M. Corti, “Approximating the Worst-Case Execution of Soft Real-Time Applications”, PhD Thesis, Swiss Federal Institute of Technology (ETH) Zurich, March

[29]  J. Gustafsson, B. Lisper, C. Sandberg, N. Bermudo, “A tool for automatic flow analysis of C-programs for WCET calculation”, In Bob Werner, editor, Proc. 8th IEEE International Workshop on Object-oriented Real-time Dependable Systems , Guadalajara, Mexico,

[30]  C. A. Healy. D. B. Whalley, “Tighter timing predictions by automatic detection and exploitation of value-dependent constraints”, In Proc. Real-Time Technology and Applications Symposium, pages 79–88 IEEE, Jun

[31]  W. H. Harrison, “Compiler analysis of the value ranges for variables”, IEEE Transactions on Software Engineering, SE-3(3):243-250,

[32]  M. Obitko, “Introduction to genetic algorithms, University of Applied Sciences, Czech technical university of parague,

[33]  V. R. Vemuri, “Genetic algorithms”, Computer Society meeting, Department of Applied Science University of California, Davis Livermore, CA, Ottawa,

[34]  K. A. Dejong and W. M. Spears. “Using genetic algorithms to solve NP-complete problems”, Proc. of the Third Int. Conf. on Genetic Algorithms,

[35]  J. L. Sobral and A. J. Proença, “Dynamic Grain-Size Adaptation on Object Oriented Parallel Programming The SCOOPP Approach” Universidade do Minho, 4710 Braga, PORTUGAL,

[36]  Y. Gourhant, S. Louboutin and V. Cahill, “Dynamic Clustering in an Object-Oriented Distributed System” Trinity College , bublin 2 , Ireland , October 9,

[37]  R. E. Diaconescu, L. Wang and M. Franz, “Automatic Distribution of Java Byte Code Based on Dependence Analysis” University of California, Irvine,

مقدمه

  در سال های اخیر صنعت کامپیوتر رشد بسیار شگفت انگیزی داشته است. در طی دو دهه اخیر سرعت کامپیوتر های شخصی از چند دستور در ثانیه به چند میلیون دستور در ثانیه رسیده است در صورتی که قیمت آنها نیز از چند میلیون دلار به چند هزار دلار کاهش یافته است

  افزایش نیاز به  سیستم هایی با کارائی بسیار زیاد و سرعت فوق العاده بالای شبکه ها (شبکه های ترابیتی)  سبب جلب علاقه محققان به پردازش های موازی و توزیع شده، شده است. از جمله دلایل افزایش توجه به سیستم های توزیع شده می توان به موارد زیر اشاره کرد

1: پیشرفت تکنولوژی پردازش

2: سرعت بالای شبکه ها

3: انجام تحقیقات گسترده برای ارائه محیطهائی برای انجام محاسباتی توزیع شده

  بعلاوه به نظر می رسد با افزایش  روزافزون نیاز به توان پردازشی سریعتر، هیچ بستر محاسباتی منفرد،  نمی تواند پاسخگوی این نیاز باشد بنابراین محیطهای پردازشی آتی باید بتواننداز منابع محاسباتی نا همگن موجود در شبکه استفاده کنند. فقط سیستم های موازی و توزیع شده امکان استفاده از  منابع مختلف موجود در شبکه را میسر می کنند

 از سوی دیگر تحول چشم گیری نیز در صنعت شبکه های کامپیوتری به وجود آمده است. امروزه هزاران کامپیوتر می توانند از طریق یک شبکه LAN به یکدیگر متصل شده و در کسری از ثانیه داده های خود را با یکدیگر مبادله کنند. یا به کمک یک شبکه WAN میلیون ها کامپیوتر از سرتاسر دنیا  قادر به تبادل داده با یکدیگر هستند.با توجه به این تحولات، امروزه تصور مجموعه ای از کامپیوتر ها که به صورت یک کامپیوتر یکپارچه  اما با قدرت بسیار بیشتر ،چندان بعید نیست

    فصل اول

 مفاهیم اولیه

مقدمه

1-1 سیستم های توزیع شده

در حالت کلی تعریف زیر را می توان برای یک سیستم توزیع شده ارائه کرد

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

  مزایا و معایب سیستم های توزیع شده

  سیستم های کامپیوتری توزیع شده به وسیله پژوهشگران به طور گسترده مطالعه شده و مزایای زیادی در رابطه با آن گزارش شده است. به عنوان مثال پیشرفت های اخیر در تکنولوژی  شبکه ها و پردازه ها، دستیابی به مزایای زیر را امکان پذیر ساخته است

1 افزایش کارایی: وجود چندین کامپیوتر در یک سیستم توزیع شده به برنامه کاربردی امکان پردازش و اجرا به صورت موازی را می دهد بنابراین سرعت اجرای برنامه کاربردی و کارایی سیستم افزایش می یابد برای مثال کارایی یک سیستم فایل می تواند به وسیله تکرار توابع آن بر روی چندین کامپیوتر بیشتر شود. تکرار سیستم فایل باعث می شود چندین برنامه کاربردی به سیستم فایل به صورت موازی دسترسی داشته باشند بعلاوه تکرار فایل ها ترافیک شبکه را بین سایت های مختلف توزیع کرده و تاخیر ناشی از صف بندی را کاهش می دهد

2 به اشتراک گذاری منابع: به اشتراک گذاری منابع مقرون به صرفه بودن و امکان دسترسی کارا به منابع سیستم را فراهم میکند یعنی کاربران در عرض چند دقیقه می توانند منابع سخت افزاری و نرم افزاری گران و خاص منظوره را مانند سرورهای پایگاه داده ها، سرورهای پردازش، سرورهای پرینترو; را به اشتراک بگذارند

3 افزایش توسعه پذیری: سیستم های توزیع شده می توانند به صورت سازگار با محیط طراحی شوند مثلا برای یک محاسبه سنگین، سیستم خود را به گونه ای سازمان دهی می کند که شامل تعداد زیادی از کامپیوترها و منابع باشد در صورتیکه برای پردازشهای کوچکتر  فقط از چند منبع استفاده خواهد کرد بعلاوه در صورت لزوم محدودیتهائی مانند ظرفیت سیستم فایل و قدرت محاسبتی سیستم را می توان به سادگی با اضافه کردن کامپیوترها یا سرورهای بیشتر افزایش یابد

4 افزایش قابلیت اطمینان، دسترسی راحت و تحمل پذیری خطا:  وجود چندین منبع ذخیره سازی و محاسباتی در یک سیستم، ساخت سیستم توزیع شد تحمل پذیر خطا را مقرون به صرفه و جالب می کند

سیستم می تواند خرابی یک کامپیوتر را به وسیله تخصیص  وظایف آن به کامپیوتر دیگر تحمل کند بعلاوه سیستم می تواند به وسیله تکرار توابع یا منابع، در کامپیوتر های مختلف،  خطر از دست دادن آنها  را برطرف کند

5 مقرون به صرفه گی: کارایی کامپیوترها تقریباً هر دو سال یک بار دو برابر شده، در صورتیکه قیمت آنها در دهه اخیر تقریبا در هر سال نصف شده است بعلاوه  شبکه هایی با سرعت بسیار زیاد نیز به وجود آمده است که ساخت سیستم های توزیع شده را نسبت به سیستم های موازی بر اساس نرخ قیمت به کارایی مقرون به صرفه تر کرده است

البته این پیشرفت ها به آسانی به دست نمی آید زیرا طراحی یک سیستم توزیع شده همه منظوره بسیار مشکلتر از طراحی یک سیستم متمرکز است. در طراحی یک سیستم توزیع شد چند منظوره تعداد زیادی از گزینه ها و مسائل باید در نظر گرفته شوند که پیکر بندی فیزیکی سیستم ،خصوصیات بستر محاسباتی، شبکه ارتباطی، زمان بندی وظایف، سیاست های تخصیص منابع و مکانیزم کنترل آن ها، ایجاد سازگاری و کنترل همروندی و امنیت، نمونه هایی از آنهاست. این مشکلات را می توان  ناشی از عدم بلوغ سیستم های توزیع شده، ناهماهنگی و رفتار مستقل کامپیوترها، پراکندگی جغرافیایی منابع سیستم و; دانست. این مشکلات در  زیر خلاصه شده اند

   1  فهم کامل تئوری محاسبات توزیع شده هنوز صورت نگرفته است. این موضوع نسبتاً جدید بوده و ما، قبل از اینکه به تئوری طراحی چنین سیستم های پردازشی تسلط پیدا کنیم باید تعداد زیادی سیستم توزیع شده معتبر با اهداف معمول و معماری های متفاوت را طراحی و آزمایش کنیم

   2 رفتار ناهماهنگ و مستقل منابع سیستم یا اجزای آن، کنترل نرم افزار را پیچیده می کند در حالیکه این امر در یک سیستم متمرکز محاسباتی کار ساده ای است. اگر کامپیوترها به صورت مشتری-خدمتگذار سازماندهی شوند، کنترل  نرم افزار ساده تر و رفتار آن قابل پیش بینی تر خواهد بود با این حال این ساختار با یکی از مشخصات سیستم های توزیع شده که همان مستقل بودن کامپیوترها و اجرای آسنکرونن می باشد در تناقض است

  3 استفاده از شبکه های ارتباطی برای اتصال کامپیوترها به یکدیگر مرحله دیگری از پیچیده گی را معرفی می کند. طراحان سیستم توزیع شده نه تنها باید در طراحی سیستم های کامپیوتری و سیستم های نرم افزاری و سرویس ها ماهر باشد بلکه در طراحی شبکه ارتباطی مطمئن، ایجاد همزمانی ، سازگاری و برطرف کردن خطاها در یک سیستم پیچیده از کامپیوترهای ناهمگن و پراکنده از نظر جغرافیایی نیز تسلط داشته باشند. تعداد منابع استفاده شده در چنین سیستمهائی می تواند دهها، صدها و یا حتی هزاران منبع محاسباتی و ذخیره سازی باشد

 یک سیستم توزیع شده حداقل بایداهداف زیر را برآورده کند:      1- به سادگی منابع موجود در شبکه را در اختیار کاربران قرار دهد

2- کاربران نباید از این موضوع که منبع مورد استفاده آنها در کامپیوتر دیگری در شبکه قرار دارد مطلع شوند.(شفافیت)   3- سیستم توزیع شده باید باز باشد

4- سیستم توزیع شده باید مقیاس پذیر باشد

شفافیت می تواند در جنبه های مختلف سیستم های توزیع شده مطرح شود

دستیابی: پنهان سازی تفاوت در ذخیره سازی داده ها و نحوه دسترسی به یک منبع
محل : پنهان سازی مکان واقعی منابع در شبکه
مهاجرت:  پنهان سازی تغییر محل منابع یعنی در صورت تغییر محل منبع، کاربران از این امر مطلع نگردند
تجدید محل: پنهان سازی مهاجرت یک منبع در حال استفاده، از کاربر آن
تکرار: پنهان سازی تکرار منابع به گونه ای که کاربران از این امر مطلع نگردند
همروندی: پنهان سازی استفاده اشتراکی از یک منبع بین چند کابر. به گونه ای که کاربران احساس می کنند تنها استفاده کننده منبع می باشند
خطا: پنهان سازی بروز خطا در یک منبع و برطرف سازی آن از دید کاربران. به عبارتی کاربران از بروز خطا در قسمتی از سیستم و برطرف سازی آن آگاه نمی شوند
یکی از اهداف دیگر سیستم های توریع شده مخفی کردن این واقعیت از دید کاربران است که منابع مورد استفاده آنها در بین کامپیوتر های مختلف توزیع شده است. سیستمی که بتواند این مخفی سازی را به خوبی انجام دهد شفافیت گفته می شود

 مسائل مربوط به مقیاس پذیری نیز تا حد زیادی به میزان مولفه های متمرکز سیستم بستگی دارد. هر چه این میزان زیاد باشد مقیاس پذیر کردن سیستم مشکل تر خواهد بود

با وجود این مشکلات موفقیت های محدودی در طراحی سیستم های توزیع شده با اهداف خاص مانند سیستم های بانکداری، سیستم حمل و نقل و انبارداری توزیع شده  به دست آمده است. با این حال طراحی یک سیستم توزیع شده  مطمئن همه منظوره که هم مزایای سیستم های متمرکز (استفاده و  مدیریت ساده ویکپارچگی) و هم مزایای سیستم های شبکه ای (وجود ارتباطات،توسعه پذیری ، قیمت وکارائی) را دارد هنوز هم یک کار چالش انگیز است

 انگیزش

      ایده شی گرایی از محبوب ترین روش های تولید نرم افزار است,که برای طراحی، توصیف و پیاده سازی سیستم های توزیع شده نیز بسیار سودمند است.[11] مزیت این روش برای ساخت سیستم های توزیع شده این است که میتوان کدهای برنامه را در اشیا کپسوله کرده و سپس اشیا را به ماژول های مستقلی دسته بندی کرد و هر ماژول را بر روی یک منبع محاسباتی مجزا مستقر نمود. با این حال به عنوان یک اصل [8]تولید یک برنامه توزیع شده، همواره سخت تر از ایجاد یک برنامه غیر توزیع شده است, که عملکردی معادل آن را دارد. به طوری که ساخت یک سیستم توزیع شده میتواند به یک کار خسته کننده  و مملو از خطا تبدیل شود.[4] با وجود اینکه امروزه  ابزار ها و تکنیک های بسیار مفیدی مانند[29] RPC ،[15] CORBA و[8] DCOM جهت ساخت سیستم های توزیع شده با کارایی بالا ارائه گشته اند، اما در حالت کلی فرایند ساخت یک سیستم توزیع شده از بدو پیدایش سیستم های توزیع شده تغیر اندکی کرده است : برنامه نویس برنامه را به ماژول های مختلفی تقسیم کرده، هر ماژول را به صورت مجزا پیاده سازی کرده و امکان برقراری ارتباط بین آنها را ایجاد می کند و در نهایت هر ماژول را  در یک کامپیوتر مستقل در شبکه مستقر میکند. برخی از چالش هایی که در رابطه با ساخت سیستم های توزیع شده پیش روی یک برنامه نویس یا طراح نرم افزار می تواند قرار گیرد عبارت اند از

پیچیدگی طراحی و پیاده سازی سیستم های توزیع شده
پیدایش نوع جدیدی از خطاها مانند خطاهای ناشی ازهمروندی و  همگام سازی پردازه ها
مشکلات ناشی از سازگاری داده ها  در کل سیستم
موازنه کار  بارگذاری شده در منابع موجود در سیستم

      لذا اتوماتیک سازی فرایند تبدیل یک برنامه ترتیبی به یک برنامه قابل اجرا برروی یک محیط محاسباتی توزیع شده همواره به عنوان یک مساله باز تحقیقاتی مطرح بوده است. امروزه شبکه‌های کامپیوتری به واسطه پیشرفت تکنولوژی ارتباطات  توانسته‌اند جایگزین کامپیوترهای گران قیمت موازی­­گردند[1]

هنگام طراحی برنامه های توزیع شده برای مسائل کاربردی، اغلب الگوریتم ها به مجموعه ای از کارهای کلاسیک، و تکراری  تجزیه می شوند. از جمله کارهای بنیادی که در اغلب الگوریتم ها دیده می شوند می توان به انتشار[1] اطلاعات به تمام گره ها،ارسال پیام به برخی از گره ها[2]، سنکرون سازی عمومی تمام پردازه ها، شروع اجرای برخی رویداد ها، ضمن اجرای پردازه ها، یا انجام محاسبه ای که داده های مورد نیاز آن بین گره های مختلف توزیع شده، اشاره کرد. این عملیات ها معمولا با تبادل پیام بین پردازه ها انجام می گیرند.با طراحی زیر ساختی که بتواند این primitive ها را در اختیار برنامه های ترتیبی قرار دهد می توان نسخه توزیع شده ای از یک برنامه ترتِبی تولید کرد

یکی از چالشهای مطرح در توزیع کد، میزان تسریع حاصل از توزیع می‌باشد[4] برنامه های علمی نیاز به کامپیوترهایی با توان محاسباتی بالا دارند. این نوع کامپیوترها معمولا بسیار گران قیمت میباشند. امروزه سعی برآن است تا بجای استفاده از سوپرکامپیوترها از شبکه ای با کامپیوترهای ارزان قیمت برای حل مسائل علمی استفاده شود. هدف ما توزیع کد برنامه ها جهت حصول حداکثر میزان همروندی در اجرای کد است در صورت موفقیت مسلما زمان اجرایی به حداقل ممکن کاهش خواهد یافت

محاسبه زمان اجرای یک برنامه بصورت دقیق امکان ندارد، چون برحسب مسیرهای اجرایی[3] متفاوت در یک برنامه، زمان اجرای آن متفاوت خواهد بود. بیشترین و کمترین زمان اجرای یک برنامه، به طولانی‌ترین و کوتاهترین مسیر اجرایی برنامه از لحاظ زمانی بستگی خواهد داشت. هدف از یافتن اطلاعات مسیرهای اجرایی یک برنامه، تخمین زمان اجرای آن است

  همانطور که بیان شد توزیع کد با هدف افزایش سرعت پردازش صورت می‌گیرد. بنابراین انتظار می‌رود کد توزیع شده نسبت به قبل سریعتر اجرا­ گردد. نکته قابل تامل این است که آیا توزیع صورت گرفته باعث تسریع شده است؟ میزان تسریع (تقویت توزیع) چقدر است؟ برای پاسخ به این سوالات باید مشخص گردد مدت زما ن اجرای برنامه، قبل و بعد از توزیع به چه میزان بوده است

به هنگام توزیع، بخشی از برنامه در ایستگاه کاری راه دور اجرا می‌گردد. برای محاسبه زمانِ اجرای برنامه ترتیبی توزیع شده، باید مدت زمانیکه طول می کشد تا افراز[4] احضار شده در ایستگاه کاری راه‌دور اجرا گردد و مدت زمان سپری شده بین دستور احضار[5] تا اولین استفاده از نتیجه این احضار، تخمین زده شود و بر اساس مدت زمان احضار و ارسال نتایج، زمان اجرای توزیع شده محاسبه گردد. بعنوان مثال در مرجع [4] میزان تسریع توزیع محاسبه شده است. این عامل بر اساس زمان محاسبه شده  دو ایستگاه کاری بر روی لبه اتصال دهنده آنها، مشخص می شود

1-3-  مراحل کلی تبدیل برنامه ترتیبی به برنامه توزیع شده

در حالت کلی برای تبدیل  یک برنامه ترتیبی به یک برنامه توزیع شده مراحل زیر پیموده می شود

-         با پیمایش برنامه ترتیبی توسط یک تجزیه گر ویژه که از کلاس های کتابخانه[7] COMPOST استفاده میکند، اطلاعات لازم جهت ساخت گراف وابستگی کلاس ها،  خوشه بندی ، برآورد زمان اجرای متد های برنامه و ایجاد کد توزیع شده  در قالب سه کدخلاصه  با نام های SourceModel ، DepModel و CostModel استخراج می گردد. در این مرحله علاوه بر خلاصه سازی اطلاعات برنامه, نقاط همگام سازی برنامه نیز تعیین می گردد. یک نقطه همگام سازی مکانی درمتن برنامه است که درآن یکی از نتایج یک فراخوانی متد دور استفاده شده است.  نتایج به دست آمده از این مرحله مستفیما در هر یک از مراحل  بعدی استفاده می شوند

-         پس از استخراج اطلاعات لازم ، گراف فراخوانی متد های برنامه ترتیبی با استفاده از اطلاعات موجود در  کد خلاصه  SourceModel یا مدل منبع, استخراج و رسم می شود. در محیط پیاده سازی شده, استخراج گراف فراخوانی به سه روش[5] CHA ، RTA و FRTA  امکان پذیر است

-         پس از ساخت گراف فراخوانی به کمک الگوریتمی که مدت زمان بین فراخوانی یک متد و استفاده از یکی از نتایج اجرای  آن را محاسبه می کند, یال های موجود در گراف فراخوانی توابع  به گونه ای وزن دار میشوند که وزن یک یال میزان افزایش کارایی برنامه در صورت فراخوانی آن متد  به صورت آسنکرون  را نشان دهد. جهت انجام این کار دو الگوریتم دیگر که یکی مدت زمان اجرای یک متد و دیگری مدت زمان اجرای یک تکه کد را برآورد می کند طراحی وپیاده سازی شده اند.  بر آورد زمان اجرای متدها از طریق یکی دیگر از کد های خلاصه تولید شده در مرحله اول به نام CostModel صورت می گیرد. در این پایان نامه برآورد زمان اجرای یک تکه کد به کمک برآورد میزان پیچیدگی آن انجام می شود

-         پس از وزن گذاری یال های موجود درگراف فراخوانی و استخراج گراف وابستگی بین کلاس ها، این گراف به گونه ای خوشه بندی می شود که کلاس هایی با حد اکثر درجه همبستگی در یک خوشه قرار گیرند و همچنین میزان کلاس های بار گذاری شده در هر خوشه متناسب و ارتباط بین خوشه ها تا حد امکان کم باشد به عبارت دیگر خوشه ها دارای خصوصیت Load Balancing بوده و تعداد فراخوانی های بین خوشه ای تا حد امکان کم باشد.  در سیستم پیاده سازی شده فرایند خوشه بندی می تواند به صورت کاملا اتوماتیک توسط سیستم یا نیمه اتوماتیک انجام گیرد. در حالت دوم کاربر می تواند تغییرات مورد نظر خود را در خوشه بندی کلاس ها اعمال کند . درحالت اول نیز به کمک یک الگوریتم تعیین تعداد خوشه های بهینه [18] ، ساختار و تعداد خوشه های بهینه برای کلاس های برنامه مشخص می شود

-         در نهایت پس از مشخص شدن خوشه های برنامه، کد توزیع شده تولید می شود. برای این منظور یک شی Proxy به هر یک از خوشه ها تخصیص می یابد که این شی مدیریت ایجاد اشیا دور و فراخوانی متد های آنها را بر عهده می گیرد. یک شی Proxy  جهت ایجاد اشیا دور و مدیریت فراخوانی متد های آنها از دو شی دیگر به نام های Object Manager و Synchronizer استفاده می کند. این اشیا نیز  از کلاس های کتابخانه Java Symphony جهت انجام وظایف خود استفاده می کند

-     با تحلیل متن برنامه ترتیبی و با توجه به نتیجه خوشه بندی، تمام دستورات ایجاد اشیا، و فراخوانی متد هایی که کلاس آنها در خوشه دیگری قرار گرفته با فراخوانی متد های مناسبی از شی Proxy تعویض می شوند. همچنین با استفاده از آنالیز وابستگی داده ها نقاطی از برنامه ترتیبی که در آنها باید همگام سازی صورت گیرد کشف شده و کد های مناسبی در آن نقاط از برنامه درج می شود

 ساختار پایان نامه

   فصل های بعدی در این پایان نامه به شرح زیر سازماندهی شده اند. در فصل دوم تحقیقات و ابزارهای  مرتبط با این پروژه و نحوه استخراج کد خلاصه شده از متن برنامه جهت ساخت گراف فراخوانی متد ها ، بررسی شده اند.  همچنین انواع روشهای خوشه بندی برای رسیدن به اهداف مختلف با در نظر گرفتن پارامترهای متفاوتی از قبیل محدودیت دسترسی به منابع ، پیوستگی، چسبندگی و تعداد فراخوانیهای بین اشیا، وزن اشاره گرها و غیره نیز بررسی شده است

 در فصل سوم نحوه وزن گذاری گراف فراخوانی استخراج شده و ساخت گراف کلاس های برنامه بررسی شده است. در این فصل  به بررسی روشهای مختلف تخمین زمان اجرای برنامه ها پرداخته خواهد شد که شامل مفاهیم مرتبط با تخمین زمان اجرای برنامه در تحلیل ایستا ، رعایت میزان دقت تخمین زمان اجرا برنامه، معیارهای موجود در تخمین زمان اجرا و راه حلهای بهینه در حالتهای پیش آمده پرداخته خواهد شد

 وزن گذاری  به گونه ای صورت میگیرد که وزن هر یال نشان دهنده میزان افزایش در کارایی سیستم در صورت همروندی توابع موجود در گره های آن یال باشد

در فصل چهارم نحوه خوشه بندی گراف وابستگی استخراج شده توسط تکنیک های خوشه بندی سلسله مراتبی[4] و یافتن تعداد خوشه های بهینه برای کلاس های برنامه ترتیبی توصیف شده است. و در فصل پنجم به نحوه پیاده سازی و ارزیابی روش پیشنهادی پرداخته خواهد شد که ابتدا نمودار کلاسها و فعالیت آنها بررسی شده و جهت تکمیل مطالب این قسمت، نمودار اشیای حاصل از کلاسهای مورد استفاده در ادامه آورده خواهد شد و روش پیشنهادی توسط مسئله فروشنده دوره گرد و مقایسه آن با سایر روش ها ارزیابی می شود

در فصل ششم با نتیجه گیری از مطالب و نیز بیان کارهای آتی به پایان نامه خاتمه می دهیم

جمع بندی

  در این فصل دلایل نیاز به یک توزیعگر اتوماتیک، کار های مرتبط انجام شده با این موضوع  و  ساختار کلی محیط پیاده سازی شده جهت تبدیل برنامه های ترتیبی به نسخه های توزیع شده از همان برنامه بررسی گردید. همانطور که گفته شد برای تبدیل یک برنامه ترتیبی به یک برنامه توزیع شده متن برنامه ترتیبی ابتدا به کمک کتابخانه Compost تحلیل شده گراف فراخوانی، از متن برنامه استخراج می شوند. سپس با برآورد زمان اجرای متد ها و تخمین زمان صرفه جویی شده در اجرا در صورت توزیع آنها، یال های موجود در گراف فراخوانی وزن دار شده و گراف وابستگی کلاس های برنامه ساخته می شود. پس از ساخت گراف فراخوانی این گراف توسط یک الگوریتم خوشه بندی سلسله مراتبی ویژه  خوشه بندی شده و پس از مشخص شدن وضعیت و تعداد خوشه ها با تخصیص یک شی Proxy به هر خوشه و کشف نقاط همگام سازی، برنامه ترتیبی به یک برنامه توزیع شده تبدیل می شود. ترجمه کد های ترتیبی به توزیع شده نیز به کمک کتابخانه کلاس های Compost صورت می گیرد

فصل دوم

 تکنیک ها و ابزارهای مرتبط