نوع فایل: word
قابل ویرایش 140 صفحه
چکیده:
با توجه به تحولات اخیر در تکنولوژی ارتباطات و نیاز روز افزون به توان پردازشی زیاد ، امروزه تصور مجموعه ای از کامپیوتر ها که به صورت یک کامپیوتر یکپارچه ،اما با قدرت بسیار بیشتر در حال کار هستند چندان بعید نیست. یک برنامه توزیع شده می تواند به صورت مجموعه ای از پردازه های در حال اجرا که با تبادل پیام از طریق شبکه ارتباطی با یکدیگر همکاری می کنند تعریف شود.
با این حال همواره بعنوان یک اصل، ساخت یک برنامه توزیع شده مشکلتر از برنامه متمرکز است. از جمله عواملی که باعث افزایش این پیچیدگی میشود مواجه شدن با برنامه نویسی تحت شبکه، همگام سازی پردازه ها، حل مساله انحصار متقابل بین آنها، افزایش تحمل پذیری خطا و اشکال زدایی میباشد. یکی از روش های مورد توجه در ساخت سیستم های توزیع شده، تبدیل اتوماتیک برنامه های ترتیبی به برنامه های توزیع شده است.
در این پایان نامه روشی جدید برای توزیع اتوماتیک برنامه های ترتیبی با خوشه بندی کلاس های آن صورت می گیرد.تکنیک های خوشه بندی متنوعی تا کنون برای این منظور استفاده شده است که پس از بررسی مزایا و معایب هر یک روش جدیدی برای خوشه بندی معرفی شده است. پس از خوشه بندی معماری طوری بازسازی میشود که حداکثر همروندی در اجرای قطعات توزیع شده ایجاد شود لذا در این پروژه روشی برای بازسازی معماری سیستم های توزیعی علمی با ایجاد حداکثر همروندی در اجرای کد برنامه ها ارائه خواهد شد.
مقدمه:
فهرست مطالب:
مقدمه
فصل اول - مفاهیم اولیه
سیستم های توزیع شده
مزایا و معایب سیستم های توزیع شده
انگیزش
مراحل کلی تبدیل برنامه ترتیبی به برنامه توزیع شده
ساختار پایان نامه.
جمع بندی
فصل دوم - تکنیک ها و ابزارهای مرتبط
2-1.ابزارهای تبادل پیام در مقایسه با حافظه اشتراکی توزیع شده
2-1-1. تبادل پیام.
2-1-2. خصوصیات مطلوب یک سیستم تبادل پیام
2-1-3. طبقه بندی ابزارهای تبادل پیام
2-2. توزیعگر های اتوماتیک
2-2-1. ابزار های نیمه اتوماتیک
2-2-2. ابزار های تمام اتوماتیک
2-2-3. توزیع بایت کد جاوا بر مبنای تحلیل وابستگی به صورت اتوماتیک
2-4. مطابقت اندازه گره در محیط برنامه نویسی شی گرا به صورت پویا توسط روش اسکوپ
2-5.افرازبندی در سیستم توزیع شده شی گرا به صورت پویا
2-5-1. معیارهای دسته بندی اشیاء
2-5-2. الگوریتم خوشه بندی مشتق شده از الگوریتم حریصانه lo,s
2-5-3. دسته بندی اشیاء موجود در خوشه ها
2-6. نتیجه گیری
فصل سوم - استخراج گراف فراخوانی
ساخت گراف جریان فراخوانی
3-2-1. الگوریتم های تعین مقصد فراخوانی
3-2-2. روش آنالیز نوع ایستاتیک
روش آنالیز سلسله مراتب کلاس
3-2-3. روش آنالیز نوع سریع
3-2-4. روش آنالیز نوع سریع حساس به جریان برنامه
استخراج گراف فراخوانی جهت ساخت گراف کلاسها
مقایسه روش های ساخت گراف فراخوانی
وزن گذاری گراف فراخوانی
استراتژی وزن گذاری یال های گراف فراخوانی توابع
برآورد زمان اجرای کد های ترتیبی
3-7-1. روش های برآورد زمان اجرای کد های ترتیبی
3-7-2. برآورد زمان اجرای کدهای برنامه باآنالیز متن برنامه
3-7-3. تخمین ایستای زمان اجرای برنامه ها
3-7-4. تعیین سرحد تکرار حلقه ها و فراخوانی های بازگشتی
3-7-5. حذف مسیرهای اجرا نشدنی
3-7-6. بهینه سازی کامپایلرها و تخمین زمان اجرای برنامه
زبان های برنامه سازی و تخمین زمان اجرا
رعایت میزان دقت تخمین در زمان اجرا
معیارهای موجود در تخمین طولانی ترین زمان اجرا
3-10-1. تحلیل جریان داده
3-10-2. تحلیل کاهش بازگشتی
3-10-3. حجم زیاد اطلاعات
3-10-4. استفاده از کد Object برنامه
بایت کد جاوا و محاسبه زمان اجرای دستورالعملها
محاسبه زمان اجرای حلقه ها
3-12-1. نحوه شناسایی حلقه های تکرار
انتشار دامنه مقادیر
دستورات شرطی و نحوه شناسایی آنها
محاسبه زمان اجرای کل برنامه با استفاده از روش پیشنهادی
3-15-1. تشخیص حلقه های تکرار
3-15-2. تخمین تعداد تکرار حلقه ها
3-15-3. انتشار مقادیر
3-15-4. محاسبه زمان اجرای توابع موجود در یک دور از گراف
یافتن نقاط همگام سازی
بررسی نتیجه الگوریتم پیشنهادی برروی یک برنامه نمونه
جمع بندی
فصل چهارم - خوشه بندی
مقدمه
خوشه بندی سلسله مراتبی
خوشه بندی سلسله مراتبی پایین به بالا (تلفیق)
روش های ادغام خوشه ها در خوشه بندی پایین به بالا
4-4-1. Single Linkage
4-4-2. Complete Linkage
4-4-3. Group Average Linkage
4-4-4. Simple Average Linkage
4-4-5. Weighted Average Linkage
4-4-6. سه روش مفید دیگر (Median, Centroid, Wards )
تکنیک های یافتن تعداد خوشه های بهینه
4-5-1. جدول تلفیق (جدول ادغام)
4-5-2. تراز تلفیق
4-5-3. نمودار dendrogram
4-5-4. تعیین تعداد خوشه های بهینه
تکنیک های پیدا کردن نقطه پیچش در نمودار جدول تلفیق
روش پیشنهادی در این پایان نامه جهت خوشه بندی
4-7-1. الگوریتم پیشنهادی برای خوشه بندی کلاس ها
جمع بندی
فصل پنجم - پیاده سازی و ارزیــابــی
محیط پیاده سازی شده
مقایسة روش خوشه بندی پیشنهادی با روش حریصانه متداول
فصل ششم - نتیجـه‌گیـری
نتیجه گیری
کارهای آتی
منابع و مراجع
فهرست شکلها
3-1. یک برنامه نمونه و گراف فراخوانی آن
3-2. الگوریتم ساخت گراف فراخوانی به روش CHA
3-3. الگوریتم انتخاب متد بعدی در روش FRTA
3-4. الگوریتم Travers برای روش FRTA
3-5. الگوریتم روش FRTA
3-6. یک برنامه نمونه ساده
3-7. گراف فراخوانی اسخراج شده با استفاده از روش CHA
3-8. الگوریتم وزن گذاری گراف فراخوانی
3-9. نمونه ای از یک ماتریس ناهمبستگی
3-10. الگوریتم برآورد زمان اجرای یک تکه کد
3-11. الگوریتم برآورد زمان اجرای یک تکه کد
3-12. مثال برای حذف مسیرهای اجرا نشدنی
3-13. حدود زمان اجرای برنامه مطرح درشبیه‌ساز San
3-14. قوانین مورد استفاده در روش شمای زمان سنجی
3-15. الگوریتم ساده برای ایجاد درخت پوشا
3-16. دو الگوریتم مجزا برای ساختن حلقه های طبیعی
3-17. الگوریتم یافتن مجموعه گره های مسلط بر هر گره در یک گراف
3-18. مثالی از انتشار مقادیر در متن یک برنامه
3-19. نمونه گراف جریان کنترلی حلقه دارای شرط
3-20. یک حلقه ساده در گراف حهت دار
3-21. روش محاسبه زمان اجرای نودها در گراف جهت دار
3-22. الگوریتم تعیین نقاط همگام سازی
3-23. گراف وابستگی برنامه فروشنده دوره گرد
3-24. تعداد فراخوانی های انجام شده بین کلاس های برنامه فروشنده دوره گرد
4-1. خوشه بندی بالا به پایین و پایین به بالا
4-2. الگوریتم کلی خوشه بندی پایین به بالا
4-3. Dissimilarity Matrix
4-4. جدول رابطه های روش های مختلف
4-5. ماتریس همبستگی 5 شی فرضی
4-6. جدول تلفیق برای اشیا شکل4-5با استفاده از روش Complete Linkage
4-7. نمودار dendogram
4-8. تخمین خوشه ها از روش نمودار Dendogram
4-9. نمودار تراز های تلفیق
4-10. نقاط قرمز رنگ به عنوان نقطه برش مناسب
4-11. نمودار تراز های تلفیق
4-12. الگوریتم خوشه بندی پایین به بالای پیشنهادی
5-1. مرحله سوم خوشه بندی برنامه فروشنده دوره گرد
5-2. مرحله یازدهم از خوشه بندی برنامه فروشنده دوره گرد
5-3. خوشه های به دست آمده از الگوریتم حریصانه برای برنامه فروشنده دوره گرد
5-3. خوشه های به دست آمده از الگوریتم حریصانه برای برنامه فروشنده دوره گرد
5-5. کاهش زمان اجرای برنامه توزیع شده نسبت به برنامه ترتیبی در ورودی های بزرگ با استفاده از الگوریتم خوشه بندی پیشنهادی
5-6. روال اجرایی برنامه فروشنده دوره گرد
منابع
منابع ومأخذ:
M. Fuad, M. J. Oudshoorn, “AdJava: Automatic Distribution of Java Applications”, the 25th Australasian Computer Science Conference, 2002.
Attali, D. Caromel, R. Guider, “A Step toward automatic distribution of java programs”, ACM-ISCOPE conference on Java Grande, 2002.
Spiegel, “Automatic Distribution of Object-Oriented Programs ”, PhD Thesis, FU Berlin, FB Mathematik und Informatik, December 2002.
Parsa, V.Khalilpoor, “Automatic Distribution of Sequential Code Using JavaSymphony Middleware”, 32nd International Conference On current Trends in Theory and Practice of Computer Science 2006.
Vijay, and H. Laurie, “Practical virtual methods call for java” Proc. of the Conf. on Object- Oriented programming, systems, languages, and applications ,2000.
Zima, “Super compilers for Parallel and Vector Computers” ACM Press, 1990.
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-9: 2000.
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, 1997.
Puschner, A. Burns: Guest Editorial, “A Review of Worst-Case Execution-Time Analysis”, Journal of Real-Time Systems, 18(2/3):115–128, May 2000.
“The Java Virtual Machine Specification”, Sun Microsystems, Inc. 1995.
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. 1998.
Gustafsson, “Analysing Execution-Time of Object-Oriented Programs using Abstract Interpretation”, PhD thesis, Uppsala University, Uppsala, Sweden, May 2000.
Kirner, “Extending Optimising Compilation to Support Worst-Case Execution Time Analysis”, PhD Thesis, Institut für Technische Informatik, Technischen Universität Wien, May 2003.
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 2004.
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, 2003.
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 1989.
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. 1998.
C, A. Healy, “Automatic Utilization of Constraints for Timing Analysis”, PhD thesis, Florida State University, July 1999.
Gustafsson, “Analysing Execution-Time of Object-Oriented Programs using Abstract Interpretation”, PhD thesis, Uppsala University, Uppsala, Sweden, May 2000.
Ermedahl, F. Stappert, J. Engblom, “Clustered Worst-Case Execution-Time Calculation”, IEEE Transactions on Computers, Vol. 54, No. 9, September 2005.
Sandberg , A. Ermedahl , J. Gustafsson , B. Lisper, “Faster WCET flow analysis by program slicing”, ACM SIGPLAN Notices, v.41 n.7, July 2006.
Altenbernd, “On the false problem in hard real-time programs”, In Proc. 8th Euromicro Workshop on Real Time Systems, pages 102–107, L’Aquila,1996.
Puschner, “Zeitanalyze von Echtzeitprogrammen”, PhD thesis, Technische Universitat, Institut fur Technische Informatik, Vienna, Austria, 1994.
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. 1995.
Schoeberl, “A time predictable Java processor”, In Proceedings of the Design, Automation and Test in Europe Conference, pages 800–805, Munich, Germany, March 2006.
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 1991.
Ananian, “Harpoon Project Compiler Intermediate Representation”, October 12, 1998, www.flex-compiler.lcs.mit.edu/Harpoon/quads/quads.htm.
Corti, “Approximating the Worst-Case Execution of Soft Real-Time Applications”, PhD Thesis, Swiss Federal Institute of Technology (ETH) Zurich, March 2005.
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, 2003.
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. 1999.
H. Harrison, “Compiler analysis of the value ranges for variables”, IEEE Transactions on Software Engineering, SE-3(3):243-250, 1977.
Obitko, “Introduction to genetic algorithms, University of Applied Sciences, Czech technical university of parague, 1998.
R. Vemuri, “Genetic algorithms”, Computer Society meeting, Department of Applied Science University of California, Davis Livermore, CA, Ottawa, 1997.
A. Dejong and W. M. Spears. “Using genetic algorithms to solve NP-complete problems”, Proc. of the Third Int. Conf. on Genetic Algorithms, 1989.
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, 1999.
Gourhant, S. Louboutin and V. Cahill, “Dynamic Clustering in an Object-Oriented Distributed System” Trinity College , bublin 2 , Ireland , October 9, 1999.
E. Diaconescu, L. Wang and M. Franz, “Automatic Distribution of Java Byte Code Based on Dependence Analysis” University of California, Irvine,
پروژه ارائه یک الگوریتم خوشه بندی برای توزیع مناسب کار و ارزیابی کارایی آن. doc
