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

توضیحات محصول

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

 

چکيده

 

با توجه به تحولات اخير در تکنولوژی ارتباطات و نياز روز افزون به توان پردازشی زياد ، امروزه تصور مجموعه ای از کامپيوتر ها که به صورت يک کامپيوتر يکپارچه ،اما با قدرت بسيار بيشتر در حال کار هستند چندان بعيد نيست. يک برنامه توزيع شده  مي تواند به صورت مجموعه اي از پردازه هاي در حال اجرا که با تبادل پيام از طريق شبکه ارتباطي با يکديگر همکاري مي کنند تعريف شود.

 با اين حال همواره بعنوان يک اصل، ساخت يک برنامه توزيع شده مشکلتر از برنامه متمرکز است. از جمله عواملی که باعث افزايش اين پيچيدگی ميشود مواجه شدن با برنامه نويسی تحت شبکه، همگام سازی پردازه ها، حل مساله انحصار متقابل بين آنها، افزايش تحمل پذيری خطا و اشکال زدايی ميباشد. يکی از روش های مورد توجه در ساخت سيستم های توزيع شده، تبديل اتوماتيک برنامه های ترتیبی به برنامه های توزيع شده است.

   در اين پايان نامه روشی جدید برای توزيع اتوماتيک برنامه های ترتیبی با خوشه بندی کلاس های آن صورت می گيرد.تکنيک های خوشه بندی متنوعی تا کنون برای اين منظور استفاده شده است که پس از بررسی مزایا و معایب هر يک روش جدیدی برای خوشه بندی معرفی شده است. پس از خوشه بندی معماري طوري بازسازي ميشود كه حداكثر همروندي در اجراي قطعات توزيع شده ايجاد شود لذا در اين پروژه روشي براي بازسازي معماري سيستم هاي توزيعي علمي با ايجاد حداكثر همروندي در اجراي كد برنامه ها ارائه خواهد شد.

واژه‌هاي کليدي

خوشه بندی ، چسبندگی ، توزيع شده گی .

 

 

 

 

 

 

 

 

 

فهرست مطالب 

عنوان                                                                                                    صفحه

       

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

 

 

 

 

 

 

 

 

 

 

 

خرید این محصول

 

خواهشمنداست در صورت عدم دریافت فایل به با یادداشت کردن کد رهگیری و مراجعه به بخش پیگیری سفارش ها با زدن کد رهگیری فایل خود را مجددا دریافت کنید در غیر این صورت جهت هر گونه مشکل با شماره ذیل پیامک و یا تلگرام بدید

پشتيباني 24 ساعته (پيامك و تلگرام)

09189431367 

 

سوالات و نظر شما در مورد این محصول