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

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

مقدمه ....................................................................................................................................................................... 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