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

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

فهرست مطالب

عنوان                                                                                                    صفحه

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