عنوان                                                                                                    صفحه

مقدمه .......................................................................................................................................................................  1

1-    فصل اول - مفاهیم اولیه ..............................................................................................   2

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

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

   1-2. انگیزش  .....................................................................................................................................................    6

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

   1-4. ساختار پایان نامه.........................................................................................................................................     9

   1-5. جمع بندی ................................................................................................................................................    10

2-     فصل دوم - تکنیک ها و ابزارهای مرتبط .......................................................................................................   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

3-5.            استراتژی وزن گذاری یال های گراف فراخوانی توابع  ......................................................................  46

3-6.             برآورد زمان اجرای كد های ترتیبی .................................................................................................  50

3-7-1.            روش های برآورد زمان اجرای كد های ترتیبی ......................................................................  51

3-7-2.            برآورد زمان اجرای کدهای برنامه باآنالیز متن برنامه................................................................  51

3-7-3.            تخمین ایستای زمان اجرای برنامه ها .......................................................................................  56

3-7-4.            تعیین سرحد تكرار حلقه­ها و فراخوانی­های بازگشتی ............................................................... 57

3-7-5.            حذف مسیرهای اجرا نشدنی ..................................................................................................  57

3-7-6.            بهینه سازی كامپایلرها و تخمین زمان اجرای برنامه ..................................................................  57

3-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.         محاسبه زمان اجرای حلقه ها ............................................................................................................ 64

3-12-1.              نحوه شناسایی حلقه های تكرار ................................................................................... 65

3-12.         انتشار دامنه مقادیر ............................................................................................................................ 67

3-13.         دستورات شرطی و نحوه شناسایی آنها .............................................................................................. 68

3-14.         محاسبه زمان اجرای کل برنامه با استفاده از روش پیشنهادی   ............................................................ 70

3-15-1.               تشخیص حلقه های تكرار ................................................................................................. 71

3-15-2.               تخمین تعداد تكرار حلقه ها .............................................................................................. 71

3-15-3.               انتشار مقادیر .................................................................................................................... 71

3-15-4.               محاسبه زمان اجرای توابع موجود در یك دور از گراف...................................................  71

3-15.         یافتن نقاط همگام سازی ................................................................................................................. 73

3-16.         بررسی نتیجه الگوریتم پیشنهادی برروی یك برنامه نمونه................................................................. 76

3-17.         جمع بندی ..................................................................................................................................... 80

4-             فصل چهارم - خوشه بندی ............................................................................................................... 81

4-1.            مقدمه ............................................................................................................................................ 82

4-2.            خوشه بندی سلسله مراتبی .............................................................................................................. 82

4-3.            خوشه بندی سلسله مراتبی پایین به بالا (تلفیق) ................................................................................. 85

4-4.            روش های ادغام خوشه ها در خوشه بندی پایین به بالا .................................................................... 88

4-4-1.                    Single Linkage.................................................................................................... 88

4-4-2.               Complete Linkage .................................................................................................. 89

4-4-3.               Group Average Linkage ...................................................................................... 89

4-4-4.               Simple Average Linkage ..................................................................................... 90

4-4-5.               Weighted Average Linkage ............................................................................... 91

4-4-6.               سه روش مفید دیگر (Median, Centroid, Wards ) .............................................. 91

4-5.            تكنیك های یافتن تعداد خوشه های بهینه ..................................................................................... 94

4-5-1.                 جدول تلفیق (جدول ادغام) ........................................................................................... 94

4-5-2.                 تراز تلفیق ...................................................................................................................... 96

4-5-3.                 نمودار dendrogram ................................................................................................ 96

4-5-4.                 تعیین تعداد خوشه های بهینه .......................................................................................... 98

4-6.            تكنیك های پیدا كردن نقطه پیچش در نمودار جدول تلفیق......................................................... 100

4-7.            روش پیشنهادی در این پایان نامه جهت خوشه بندی .................................................................. 103

4-7-1.               الگوریتم پیشنهادی برای خوشه بندی کلاس ها ............................................................ 103

4-8.            جمع بندی ............................................................................................................................... 106

5-               فصل پنجم - پیاده سازی و ارزیــابــی ....................................................................................... 108

5-1.            محیط پیاده سازی شده ............................................................................................................. 109

5-2.            مقایسة روش خوشه بندی پیشنهادی با روش حریصانه متداول.................................................... 111

6-               فصل ششم - نتیجـه‌گیـری ....................................................................................................... 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