عنوان صفحه
مقدمه ....................................................................................................................................................................... 1
- فصل اول - مفاهیم اولیه .............................................................................................. 2
1-1. سیستم های توزیع شده .................................................................................................................................. 3
1-1-1. مزایا و معایب سیستم های توزیع شده..................................................................................................... 3
1-2. انگیزش ..................................................................................................................................................... 6 1-3. مراحل کلی تبدیل برنامه ترتیبی به برنامه توزیع شده .................................................................................... 8 1-4. ساختار پایان نامه......................................................................................................................................... 9
1-5. جمع بندی ................................................................................................................................................ 10
- فصل دوم - تکنیک ها و ابزارهای مرتبط ....................................................................................................... 11
2-1.ابزارهای تبادل پیام در مقایسه با حافظه اشتراکی توزیع شده......................................................................... 13
2-1-1. تبادل پیام ......................................................................................................................................... 13
2-1-2. خصوصیات مطلوب یک سیستم تبادل پیام........................................................................................ 14
2-1-3. طبقه بندی ابزارهای تبادل پیام........................................................................................................ 14
2-2. توزیعگر های اتوماتیک ..................................................................................................................... 17
2-2-1. ابزار های نیمه اتوماتیک .............................................................................................................. 17
2-2-2. ابزار های تمام اتوماتیک ............................................................................................................. 18
2-2-3. توزیع بایت کد جاوا بر مبنای تحلیل وابستگی به صورت اتوماتیک .............................................. 21 2-4. مطابقت اندازه گره در محیط برنامه نویسی شیگرا به صورت پویا توسط روش اسکوپ ......................... 24 2-5.افرازبندی در سیستم توزیع شده شی گرا به صورت پویا ......................................................................... 25
2-5-1. معیارهای دسته بندی اشیاء ........................................................................................................... 26
2-5-2. الگوریتم خوشه بندی مشتق شده از الگوریتم حریصانه lo,s ....................................................... 27
2-5-3. دسته بندی اشیاء موجود در خوشه ها ......................................................................................... 29
2-6. نتیجه گیری ........................................................................................................................................ 30
3- فصل سوم - استخراج گراف فراخوانی ....................................................................................................... 31
2-ساخت گراف فراخوانی 3-1. ساخت گراف جریان فراخوانی ............................................................................................................ 32 3-2-1. الگوریتم های تعین مقصد فراخوانی .................................................................................. 34 3-2-2. روش آنالیز نوع ایستاتیک ................................................................................................. 34
روش آنالیز سلسله مراتب کلاس ........................................................................................................... 35
3-2-3. روش آنالیز نوع سریع ........................................................................................................37
3-2-4. روش آنالیز نوع سریع حساس به جریان برنامه ....................................................................37
3-2. استخراج گراف فراخوانی جهت ساخت گراف کلاسها ...................................................................41 3-3. مقایسه روش های ساخت گراف فراخوانی ......................................................................................... 43 3-4. وزن گذاری گراف فراخوانی ............................................................................................................ 45
- استراتژی وزن گذاری یال های گراف فراخوانی توابع ...................................................................... 46
- برآورد زمان اجرای کد های ترتیبی ................................................................................................. 50
- روش های برآورد زمان اجرای کد های ترتیبی ...................................................................... 51
- برآورد زمان اجرای کدهای برنامه باآنالیز متن برنامه................................................................ 51
- تعیین سرحد تکرار حلقهها و فراخوانیهای بازگشتی ............................................................... 57
- حذف مسیرهای اجرا نشدنی .................................................................................................. 57
- بهینه سازی کامپایلرها و تخمین زمان اجرای برنامه .................................................................. 57
- نحوه شناسایی حلقه های تکرار ................................................................................... 65
- تشخیص حلقه های تکرار ................................................................................................. 71
- تخمین تعداد تکرار حلقه ها .............................................................................................. 71
- انتشار مقادیر .................................................................................................................... 71
- یافتن نقاط همگام سازی ................................................................................................................. 73
- بررسی نتیجه الگوریتم پیشنهادی برروی یک برنامه نمونه................................................................. 76
- جمع بندی ..................................................................................................................................... 80
3-7-3. تخمین ایستای زمان اجرای برنامه ها ....................................................................................... 563-7. زبان های برنامه سازی و تخمین زمان اجرا ........................................................................................ 58 3-8. رعایت میزان دقت تخمین در زمان اجرا ............................................................................................ 58 3-9. معیارهای موجود در تخمین طولانی ترین زمان اجرا .......................................................................... 59
3-10-1. تحلیل جریان داده ............................................................................................................. 59
3-10-2. تحلیل کاهش بازگشتی .................................................................................................... 61
3-10-3. حجم زیاد اطلاعات ......................................................................................................... 62
3-10-4. استفاده از کد Object برنامه ............................................................................................ 63
3-10. بایت کد جاوا و محاسبه زمان اجرای دستورالعملها ........................................................................... 63 3-11. محاسبه زمان اجرای حلقه ها ............................................................................................................ 643-12. انتشار دامنه مقادیر ............................................................................................................................ 67 3-13. دستورات شرطی و نحوه شناسایی آنها .............................................................................................. 68 3-14. محاسبه زمان اجرای کل برنامه با استفاده از روش پیشنهادی ............................................................ 703-15-4. محاسبه زمان اجرای توابع موجود در یک دور از گراف................................................... 71
- فصل چهارم - خوشه بندی ............................................................................................................... 81
- خوشه بندی سلسله مراتبی .............................................................................................................. 82
- خوشه بندی سلسله مراتبی پایین به بالا (تلفیق) ................................................................................. 85
- روش های ادغام خوشه ها در خوشه بندی پایین به بالا .................................................................... 88
- Single Linkage.................................................................................................... 88
- Simple Average Linkage ..................................................................................... 90
- Weighted Average Linkage ............................................................................... 91
- سه روش مفید دیگر (Median, Centroid, Wards ) .............................................. 91
- تکنیک های یافتن تعداد خوشه های بهینه ..................................................................................... 94
- جدول تلفیق (جدول ادغام) ........................................................................................... 94
- تراز تلفیق ...................................................................................................................... 96
- نمودار dendrogram ................................................................................................ 96
- تعیین تعداد خوشه های بهینه .......................................................................................... 98
- تکنیک های پیدا کردن نقطه پیچش در نمودار جدول تلفیق......................................................... 100
- روش پیشنهادی در این پایان نامه جهت خوشه بندی .................................................................. 103
- الگوریتم پیشنهادی برای خوشه بندی کلاس ها ............................................................ 103
- جمع بندی ............................................................................................................................... 106
- محیط پیاده سازی شده ............................................................................................................. 109
- مقایسة روش خوشه بندی پیشنهادی با روش حریصانه متداول.................................................... 111
4-1. مقدمه ............................................................................................................................................ 824-4-2. Complete Linkage .................................................................................................. 89 4-4-3. Group Average Linkage ...................................................................................... 895- فصل پنجم - پیاده سازی و ارزیــابــی ....................................................................................... 1086- فصل ششم - نتیجـه‌گیـری ....................................................................................................... 120 6-1. نتیجه گیری ............................................................................................................................ 121 6-2. کارهای آتی .......... ............................................................................................................... 121
منابع و مراجع ........................................................................................................................................ 123
عنوان
صفحه
3-1. یک برنامه نمونه و گراف فراخوانی آن ...................................................................................................... 32
3-2. الگوریتم ساخت گراف فراخوانی به روش CHA ................................................................................... 36
3-3. الگوریتم انتخاب متد بعدی در روش FRTA ........................................................................................... 39
3-4. الگوریتم Travers برای روش FRTA ................................................................................................ 40
3-5. الگوریتم روش FRTA ........................................................................................................................... 41
3-6. یک برنامه نمونه ساده ................................................................................................................................ 44
3-7. گراف فراخوانی اسخراج شده با استفاده از روش CHA ........................................................................... 45
3-8. الگوریتم وزن گذاری گراف فراخوانی ..................................................................................................... 50
3-9. نمونه ای از یک ماتریس ناهمبستگی........................................................................................................ 50
3-10. الگوریتم برآورد زمان اجرای یک تکه کد ............................................................................................ 53
3-11. الگوریتم برآورد زمان اجرای یک تکه کد ........................................................................................... 55
3-12. مثال برای حذف مسیرهای اجرا نشدنی .................................................................................................... 57
3-13. حدود زمان اجرای برنامه مطرح درشبیه‌ساز San .................................................................................... 59
3-14. قوانین مورد استفاده در روش شمای زمان سنجی ...................................................................................... 61
3-15. الگوریتم ساده برای ایجاد درخت پوشا .................................................................................................... 65
3-16. دو الگوریتم مجزا برای ساختن حلقه های طبیعی ...................................................................................... 67
3-17. الگوریتم یافتن مجموعه گره های مسلط بر هر گره در یک گراف......................................................... 67
3-18. مثالی از انتشار مقادیر در متن یک برنامه .................................................................................................. 68
3-19. نمونه گراف جریان کنترلی حلقه دارای شرط .......................................................................................... 69
3-20. یک حلقه ساده در گراف حهت دار .......................... ..............................................................................72
3-21. روش محاسبه زمان اجرای نودها در گراف جهت دار............................................................................... 73
3-22. الگوریتم تعیین نقاط همگام سازی ......................................................................................................... 75
3-23. گراف وابستگی برنامه فروشنده دوره گرد............................................................................................... 78
3-24. تعداد فراخوانی های انجام شده بین کلاس های برنامه فروشنده دوره گرد.............................................. 79
4-1. خوشه بندی بالا به پایین و پایین به بالا ..................................................................................................... 84
4-2. الگوریتم کلی خوشه بندی پایین به بالا .................................................................................................... 86
4-3. Dissimilarity Matrix ................................................................................................................... 86
4-4. جدول رابطه های روش های مختلف ........................................................................................................ 94
4-5. ماتریس همبستگی 5 شی فرضی .............................................................................................................. 95
4-6. جدول تلفیق برای اشیا شکل4-5با استفاده از روش Complete Linkage ......................................... 95
4-7. نمودار dendogram .......................................................................................................................... 97
4-8. تخمین خوشه ها از روش نمودار Dendogram .................................................................................. 98
4-9. نمودار تراز های تلفیق ......................................................................................................................... 100
4-10. نقاط قرمز رنگ به عنوان نقطه برش مناسب ....................................................................................... 102
4-11. نمودار تراز های تلفیق ...................................................................................................................... 102
4-12. الگوریتم خوشه بندی پایین به بالای پیشنهادی .................................................................................. 104
5-1. مرحله سوم خوشه بندی برنامه فروشنده دوره گرد .............................................................................. 109
5-2. مرحله یازدهم از خوشه بندی برنامه فروشنده دوره گرد ...................................................................... 111
5-3. خوشه های به دست آمده از الگوریتم حریصانه برای برنامه فروشنده دوره گرد ................................... 112
5-3. خوشه های به دست آمده از الگوریتم حریصانه برای برنامه فروشنده دوره گرد ................................... 112
5-5. کاهش زمان اجرای برنامه توزیع شده نسبت به برنامه ترتیبی در ورودی های بزرگ با استفاده از الگوریتم خوشه بندی پیشنهادی ........................................................................................................................................... 115
5-6. روال اجرایی برنامه فروشنده دوره گرد ............................................................................................. 117
